Unit-5 Merge Sort Algorithm
Uploaded by
SkillBridgeDocsUnit-5 Merge Sort Algorithm
Uploaded by
SkillBridgeDocsMerge Sort Algorithm
Merge sort is similar to the quick sort algorithm as it uses the divide and
conquer approach to sort the elements. It is one of the most popular and
efficient sorting algorithm. It divides the given list into two equal halves, calls
itself for the two halves and then merges the two sorted halves. We have to
define the merge() function to perform the merging.
The sub-lists are divided again and again into halves until the list cannot be
divided further. Then we combine the pair of one element lists into two-
element lists, sorting them in the process. The sorted two-element pairs is
merged into the four-element lists, and so on until we get the sorted list.
Now, let's see the algorithm of merge sort.
Keep Watching
Competitive questions on Structures in Hindi
00:00/03:34
Algorithm
In the following algorithm, arr is the given array, beg is the starting
element, and end is the last element of the array.
1. MERGE_SORT(arr, beg, end)
2.
3. if beg < end
4. set mid = (beg + end)/2
5. MERGE_SORT(arr, beg, mid)
6. MERGE_SORT(arr, mid + 1, end)
7. MERGE (arr, beg, mid, end)
8. end of if
9.
10. END MERGE_SORT
The important part of the merge sort is the MERGE function. This function
performs the merging of two sorted sub-arrays that are A[beg…
mid] and A[mid+1…end], to build one sorted array A[beg…end]. So, the
inputs of the MERGE function are A[], beg, mid, and end.
The implementation of the MERGE function is given as follows -
1. /* Function to merge the subarrays of a[] */
2. void merge(int a[], int beg, int mid, int end)
3. {
4. int i, j, k;
5. int n1 = mid - beg + 1;
6. int n2 = end - mid;
7.
8. int LeftArray[n1], RightArray[n2]; //temporary arrays
9.
10. /* copy data to temp arrays */
11. for (int i = 0; i < n1; i++)
12. LeftArray[i] = a[beg + i];
13. for (int j = 0; j < n2; j++)
14. RightArray[j] = a[mid + 1 + j];
15.
16. i = 0, /* initial index of first sub-array */
17. j = 0; /* initial index of second sub-array */
18. k = beg; /* initial index of merged sub-array */
19.
20. while (i < n1 && j < n2)
21. {
22. if(LeftArray[i] <= RightArray[j])
23. {
24. a[k] = LeftArray[i];
25. i++;
26. }
27. else
28. {
29. a[k] = RightArray[j];
30. j++;
31. }
32. k++;
33. }
34. while (i<n1)
35. {
36. a[k] = LeftArray[i];
37. i++;
38. k++;
39. }
40.
41. while (j<n2)
42. {
43. a[k] = RightArray[j];
44. j++;
45. k++;
46. }
47. }
Working of Merge sort Algorithm
Now, let's see the working of merge sort Algorithm.
To understand the working of the merge sort algorithm, let's take an
unsorted array. It will be easier to understand the merge sort via an
example.
Let the elements of array are -
According to the merge sort, first divide the given array into two equal
halves. Merge sort keeps dividing the list into equal parts until it cannot be
further divided.
As there are eight elements in the given array, so it is divided into two arrays
of size 4.
Now, again divide these two arrays into halves. As they are of size 4, so
divide them into new arrays of size 2.
Now, again divide these arrays to get the atomic value that cannot be further
divided.
Now, combine them in the same manner they were broken.
In combining, first compare the element of each array and then combine
them into another array in sorted order.
So, first compare 12 and 31, both are in sorted positions. Then compare 25
and 8, and in the list of two values, put 8 first followed by 25. Then compare
32 and 17, sort them and put 17 first followed by 32. After that, compare 40
and 42, and place them sequentially.
In the next iteration of combining, now compare the arrays with two data
values and merge them into an array of found values in sorted order.
Now, there is a final merging of the arrays. After the final merging of above
arrays, the array will look like -
Now, the array is completely sorted.
Merge sort complexity
Now, let's see the time complexity of merge sort in best case, average case,
and in worst case. We will also see the space complexity of the merge sort.
1. Time Complexity
Case Time Complexity
Best Case O(n*logn)
Average Case O(n*logn)
Worst Case O(n*logn)
o Best Case Complexity - It occurs when there is no sorting required,
i.e. the array is already sorted. The best-case time complexity of
merge sort is O(n*logn).
o Average Case Complexity - It occurs when the array elements are in
jumbled order that is not properly ascending and not properly
descending. The average case time complexity of merge sort
is O(n*logn).
o Worst Case Complexity - It occurs when the array elements are
required to be sorted in reverse order. That means suppose you have
to sort the array elements in ascending order, but its elements are in
descending order. The worst-case time complexity of merge sort
is O(n*logn).
2. Space Complexity
Space O(n
Complexity )
Stable YES
o The space complexity of merge sort is O(n). It is because, in merge
sort, an extra variable is required for swapping.