EXPERIMENT-4
MERGE SORT
Aim: To perform time complexity analysis on MergeSort algorithm.
Merge Sort: Merge sort is defined as a sorting algorithm that works by
dividing an array into smaller subarrays, sorting each subarray, and then
merging the sorted subarrays back together to form the final sorted array.
Merge sort is a recursive algorithm that continuously splits the array in
half until it cannot be further divided i.e., the array has only one
element left (an array with one element is always sorted). Then the
sorted subarrays are merged into one sorted array.
Step 1: Initially divide the array into two equal halves.
Step 2: These subarrays are further divided into two halves. Now they
become array of unit length that can no longer be divided and array of unit
length are always sorted.
Step 3: These sorted subarrays are merged together, and we get bigger
sorted arrays
Step 4: This merging process is continued until the sorted array is built from
the smaller subarrays.
Applications of Merge Sort:
• Sorting large datasets: Merge sort is particularly well-suited for
sorting large datasets due to its guaranteed worst-case time
complexity of O(n log n).
• External sorting: Merge sort is commonly used in external sorting,
where the data to be sorted is too large to fit into memory.
• Custom sorting: Merge sort can be adapted to handle different
input distributions, such as partially sorted, nearly sorted, or
completely unsorted data.
Applications of Merge Sort:
• Sorting large datasets: Merge sort is particularly well-suited for
sorting large datasets due to its guaranteed worst-case time
complexity of O(n log n)
. External sorting: Merge sort is commonly used in external sorting,
where the data to be
sorted is too large to fit into memory.
• Custom sorting: Merge sort can be adapted to handle different
input distributions, such as partially sorted, nearly sorted, or
completely unsorted data.
Drawbacks of Merge Sort:
• Space complexity: Merge sort requires additional memory to
store the merged subarrays during the sorting process.
• Not in-place: Merge sort is not an in-place sorting algorithm, which
means it requires additional memory to store the sorted data. This
can be a disadvantage in applications where memory usage is a
concern.
• Not always optimal for small datasets: For small datasets, Merge
sort has a higher time complexity than some other sorting
algorithms, such as insertion sort. This can result in slower
performance for very small datasets.
MERGE SORT-:
include<iostream>
include<chrono>
using namespace std;
using namespace chrono;
void merge(int arr[], int left, int middle, int right) { int n1 = middle - left + 1;
int n2 = right - middle;
int left_array[n1]; int right_array[n2];
for (int i = 0; i < n1; i++) {
left_array[i] = arr[left + i];
}
for (int i = 0; i < n2; i++) {
right_array[i] = arr[middle + 1 + i];
}
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (left_array[i] <= right_array[j])
{
arr[k] = left_array[i]; i++;
}
else
{
arr[k] = right_array[j]; j++;
}
k++;
}
Whil e (i < n1)
{
arr[k] = left_array[i]; i++;
k++;
}
while (j < n2) {
arr[k] = right_array[j]; j++;
k++;
}
}
void mergeSort(int arr[], int left, int right) { if (left < right) {
int middle = left + (right - left) / 2;
mergeSort(arr, left, middle); mergeSort(arr, middle + 1, right);
merge(arr, left, middle, right);
}
}
int main() {
int size = 5000;
// int num = size; //Unsorted
int arr[size];
// for (int i=0; i<size; i++){
// arr[i] = num;
// num--;
// }
// For half sorted other half unsorted
for (int i = 0; i < size / 2; i++) { arr[i] = i + 1;
}
// Fill the second half in reverse order
for (int i = size / 2, j = size; i < size; i++, j--) { arr[i] = j;
}
auto start=high_resolution_clock::now();
mergeSort(arr, 0, size - 1);
auto end=high_resolution_clock::now();
auto duration= duration_cast<microseconds<(end-start);
cout << "Input Size: " << size << ", Time: " << duration.count() << " microseconds";
}
Output & Graphs:
For Unsorted array:
Size of Array Time Taken (ms)
1000 119
2000 214
3000 332
4000 443
5000 574
6000 785
7000 830
8000 954
Time exity
Comple
Unsorted
1200
1000
800
600
400
200
0
0 1000 2000 3000 4000 5000 6000 7000 8000 9000
Size of Array
For Partially Sorted Array:
Size of Array Time Taken (ms)
1000 96
2000 263
3000 516
4000 453
5000 597
6000 724
7000 844
8000 997
1200
1000
800
600
400
200
0
0 1000 2000 3000 4000 5000 6000 7000 8000 9000
Size of Array
