Sorting Algorithms
Visualizing, Designing, and Analyzing the Merge Sort Algorithm.
A complete analysis of the Merge Sort Algorithm.
What Is the Divide and Conquer Approach in the Algorithm?
Many useful algorithms are recursive in structure: to solve a given problem, they call themselves recursively one or more times to deal with closely related subproblems.
These algorithms typically follow a divide-and-conquer approach: they break the problem into several subproblems that are similar to the original problem but smaller in size, solve the subproblems recursively and then combine these solutions to create a solution to the original problem.
What Is Merge Sort?
The merge sort algorithm closely follows the divide-and-conquer paradigm. Intuitively, it operates as follows.
- Divide: Divide the n-elements sequence to be sorted into two sub-sequences of n/2 elements each recursively.
- Conquer: Sort the two sub-sequences recursively using merge sort.
- Combine: Merge the two sorted sub-sequences to produce the sorted answer.
In the case of Merge sort, the recursion “bottoms out” when the sequence to be sorted has length 1, in which case there is no work to be done since every sequence of length 1 is already in sorted order.
Note: In this article, consider sub-array and sub-sequence have same meaning. Actually there is difference between these two terms.
Assume that there are 8 elements in the array, and how divide and conquer works on these elements:
- Divide: Merge sort recursively divides 8 elements sequence(array) into two new sub-sequences containing 4 elements each. Further, these two new sub-sequences are divided into four new sub-sequences containing 2 elements each. And then finally these four sub-sequences are divided into eight new sub-sequences containing 1 element each.
- Conquer: Now sort each sub-sequence that contains a single element. As a sub-sequence that contains a single element is already sorted(8 such sub-sequences are sorted). These eight sub-sequences will get merged and then form four sorted sub-sequences. These four sorted sub-sequences form two sorted sub-sequences and these two sorted sub-sequences form a final sorted array.
- Combine: The key operation of the Merge sort algorithm is the merging of two sorted sub-sequences in the ‘Combine’ step. We merge the sub-sequences by calling an auxiliary procedure Merge(arr, l,m, r) where ‘arr’ is an array and l, m, and r are indices of the array such that l≤ m< r. The procedure assumes that the sub-arrays arr[l…m] and arr[(m+1)…r] are already in sorted order. It merges them to form a single sorted sub-array that replaces the current sub-array arr[l…r]. Note that our array contains elements from arr[0…n-1] where n is the length of the array.
Let’s Visualize the Merge Sort Algorithm by Taking An example:
Now let’s take the array with elements as 5,2,4,7,1,3,2,6 and use the Merge sort visualization to sort these elements.
- The array has an initial sequence as 5,2,4,7,1,3,2,6.
- This array is divided into two sub-arrays (5,2,4,7) and (1,3,2,6). Then again these two sub-arrays are divided into (5,2),(4,7),(1,3), and (2,6). Now these four sub-arrays are divided into eight sub-arrays (5),(2),(4),(7),(1),(3),(2), and (6).
- As a sub-array with a single element is already sorted hence we can say that all the eight sub-arrays are already sorted.
- Now Merge procedure combines these sub-arrays. Initially, (5) and (2),(4) and (7),(1) and (3),(2) and (6) are combined to form (2,5),(4,7),(1,3), and (2,6). These four sub-arrays after merge forms (2,4,5,7) and (1,2,3,6). Finally these two sub-arrays form the original sorted array (1,2,2,3,4,5,6,7)
Now Let’s Design the Merge Sort Algorithm :
To design the merge sort algorithm two procedures are required:
- mergeSort(arr,l,r): Recursively calls itself to divide the array into sub-arrays.
- merge(arr,l,m,r): Merges two sorted sub-arrays to form a single sorted sub-array.
The steps for the mergeSort procedure are as follows:
mergeSort(arr[], l, r)
If(l < r)
1.Find the middle point to divide the array into two halves: middle m = (l+r)/2
2.Call mergeSort for first half: mergeSort(arr, l, m)
3.Call mergeSort for second half: mergeSort(arr, m+1, r)
4.call merge for sorting the two halves: merge(arr, l, m, r)The following diagram explains the working of the merge procedure:
Below is the code design for the merge procedure:
Below is the code design for the mergeSort procedure:
Printing array and driver functions:
OUTPUT:
— — — — — — Merged sub-array : — — — — — —
2 5
— — — — — — — — — — — — — — — — — — — — — —
— — — — — — Merged sub-array : — — — — — —
4 7
— — — — — — — — — — — — — — — — — — — — — —
— — — — — — Merged sub-array : — — — — — —
2 4 5 7
— — — — — — — — — — — — — — — — — — — — — —
— — — — — — Merged sub-array : — — — — — —
1 3
— — — — — — — — — — — — — — — — — — — — — —
— — — — — — Merged sub-array : — — — — — —
2 6
— — — — — — — — — — — — — — — — — — — — — —
— — — — — — Merged sub-array : — — — — — —
1 2 3 6
— — — — — — — — — — — — — — — — — — — — — —
— — — — — — Merged sub-array : — — — — — —
1 2 2 3 4 5 6 7
— — — — — — — — — — — — — — — — — — — — — —Time and Space Complexity Analysis:
Divide: The divide step just computes the middle of the subarray, which takes constant time. θ(1)
Conquer: We recursively solve two subproblems, each of size n/2, which contributes 2T(n/2) to the running time.
Combine: We can see that the merge procedure on an n-element subarray takes time θ(n).
Now we can combine these three steps to find the worst-case time complexity of the merge sort algorithm:
The solution for the above recurrence relation is θ(nlogn). Hence the worst-case time complexity is θ(nlogn).
Note that in best case also the above recurrence relation holds and hence best case time complexity is same as worst case. Because merge sort always divides the array into two halves and takes linear time to merge two halves.
Space complexity: O(n).
Is Merge Sort stable?
Definition of stable : the relative order of elements with the same value is maintained.
Merge sort is a stable algorithm.
For example, let’s assume you have array elements as 5,2A,4,7,1,3,2B,6 with Merge sort. Assume 2A and 2B are the same.
When the two sorted sub-arrays (2A,3,4,5) and (1,2B,3,6) are merged into a single array (1,2A,2B,3,4,5,6,7) it preserves the original order of 2A and 2B as we check for ‘≤’ in the merge procedure.
Hence the Merge sort algorithm is stable.
Is Merge Sort In-place?
It uses extra space for sorting the array elements (in this case two temp arrays are used), hence it is not an In-place sorting algorithm.
That’s all for this article. Thank you for reading this article. I hope, you have understood the Merge-sort algorithm and its time and space complexities.
Follow Vikram Gupta for Similar Content.
Reference: Introduction to algorithms.
