DSA Merge Sort
Merge Sort
The Merge Sort algorithm is a divide-and-conquer sorting technique that divides an array into smaller arrays first, then pieces the array back together correctly to complete the sorting process.
------ IMAGE MUKAVI -----
Divide: The array is first divided into progressively smaller sub-arrays until each sub-array has just one element.
Conquer: The algorithm creates a sorted array by reassembling the array’s small components by placing the lowest values first.
Recursive construction and dismantling of the array is required to sort the array.
Every time the bars in the animation above are moved downward, it signifies a recursive call that divides the array into smaller parts. The merging of two sub-arrays is shown by the bars being raised.
This is how the Merge Sort algorithm is explained:
How it works:
1.Split the unsorted array in half to create two smaller sub-arrays.
2.As long as there are more than one elements in the current array piece, divide the sub-arrays continuously.
3.When merging two sub-arrays, the lowest value is always placed first.
4.Continue combining until no more sub-arrays remain.
Examine the illustration below to get a new understanding of how Merge Sort functions. The array is divided into ever-tinier segments until it is merged back together, as you can see. Additionally, values from each sub-array are compared throughout the merging process to ensure that the lowest value appears first.
Manual Run Through
Attempting to perform the sorting by hand will help us better grasp Merge Sort’s operation before putting it into a computer language.
Step 1: An unsorted array is the starting point, and we know that it divides in half until each sub-array has just one element. The function Merge Sort makes two calls to itself, one for each half of the array. This implies that the smallest parts will be divided first from the first sub-array.
[ 12, 8, 9, 3, 11, 5, 4]
[ 12, 8, 9] [ 3, 11, 5, 4]
[ 12] [ 8, 9] [ 3, 11, 5, 4]
[ 12] [ 8] [ 9] [ 3, 11, 5, 4]
Step 2: The first sub-array has been separated, and it is now time to combine. The first two elements to be combined are 8 and 9. Since 8 is the lowest number in the first merged sub-array, it arrives before 9.
[ 12] [ 8, 9] [ 3, 11, 5, 4]
Step 3: [12] and [8, 9] are the next sub-arrays to be combined. From the beginning, values in both arrays are compared. Since 8 is less than 12, it comes before 9 because 9 is likewise less than 12.
[ 8, 9, 12] [ 3, 11, 5, 4]
Step 4: The second large sub-array is now divided recursively.
[ 8, 9, 12] [ 3, 11, 5, 4]
[ 8, 9, 12] [ 3, 11] [ 5, 4]
[ 8, 9, 12] [ 3] [ 11] [ 5, 4]
Step 5: Since 3 is less than 11, 3 and 11 are merged back together in the same order that they are displayed.
[ 8, 9, 12] [ 3, 11] [ 5, 4]
Step 6: Split and merge the sub-array containing values 5 and 4 such that 4 appears before 5.
[ 8, 9, 12] [ 3, 11] [ 5] [ 4]
[ 8, 9, 12] [ 3, 11] [ 4, 5]
Step 7: The rightmost two sub-arrays are combined. To produce elements in the newly combined array, comparisons are made:
- 3 is lower than 4
- 4 is lower than 11
- 5 is lower than 11
- 11 is the last remaining value
[ 8, 9, 12] [ 3, 4, 5, 11]Step 8: The two sub-arrays that are left together are combined. Let’s take a closer look at the comparison process used to produce the newly combined and sorted array:
3 is lower than 8:
Before [ 8, 9, 12] [ 3, 4, 5, 11]
After: [ 3, 8, 9, 12] [ 4, 5, 11]
Step 9: 4 is lower than 8:
Before [ 3, 8, 9, 12] [ 4, 5, 11]
After: [ 3, 4, 8, 9, 12] [ 5, 11]
Step 10: 5 is lower than 8:
Before [ 3, 4, 8, 9, 12] [ 5, 11]
After:[ 3, 4, 5, 8, 9, 12] [ 11]
Step 11: 8 and 9 are lower than 11:
Before [ 3, 4, 5, 8, 9, 12] [ 11]
After :[ 3, 4, 5, 8, 9, 12] [ 11]
Step 12: 11 is lower than 12:
Before [ 3, 4, 5, 8, 9, 12] [ 11]
After :[ 3, 4, 5, 8, 9, 11, 12]
The categorization is complete!
------ IMAGE MUKAVI -----
Manual Run Through: What Happened?
Recursion is not necessary to build the Merge Sort algorithm; but, as it is the most popular method, we will employ it.
Although it is not visible in the previous steps, an array is divided in half by its length, and the result is rounded down to a value we refer to as “mid.” The array is split using this “mid” value as an index.
Once the array is divided in half, the sorting function calls itself with each half, allowing for further recursive division of the array. When there is just one element in a sub-array, the splitting ceases.
The sub-arrays are combined at the conclusion of the Merge Sort function to ensure that the sub-arrays are always sorted when the array is rebuilt. The values of each sub-array are compared, and the lowest value is added to the merged array, in order to combine two sub-arrays and sort the result. Subsequently, the subsequent values in both sub-arrays are compared, with the lowest value being incorporated into the combined array.
Merge Sort Implementation
In order to apply the Merge Sort algorithm, we require:
1.a values array that requires sorting.
2.An array is given to this function, which divides it in half and calls itself with each half of the array. This process separates the arrays recursively until each sub-array has just one value.
3.An additional function that restores the sub-arrays to their sorted state.
The code that is produced looks like this:
Example
def mergeSort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
leftHalf = arr[:mid]
rightHalf = arr[mid:]
sortedLeft = mergeSort(leftHalf)
sortedRight = mergeSort(rightHalf)
return merge(sortedLeft, sortedRight)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
unsortedArr = [3, 7, 6, -10, 15, 23.5, 55, -13]
sortedArr = mergeSort(unsortedArr)
print("Sorted array:", sortedArr)
From line 6 onward, all values in the array up to and excluding the value on index “mid” are taken by arr[:mid].
Beginning at the value at index “mid” and going through all subsequent values, arr[mid:] pulls all of the values from the array on line 7.
The initial portion of the merging is completed on lines 26–27. The left or right sub-array’s remaining values can simply be added to the result array at this point after the values of the two sub-arrays are compared and it is determined that either one is empty. The outcome remains the same even if these lines are switched.
Merge Sort without Recursion
Recursion is the easiest code to implement because Merge Sort is a divide and conquer algorithm. Additionally, the recursive Merge Sort method may be simpler to comprehend and need less lines of code overall.
However, Merge Sort can also be executed without recursion, meaning that no function calls itself.
Examine the following Merge Sort implementation, which does not make use of recursion:
Example
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
def mergeSort(arr):
step = 1 # Starting with sub-arrays of length 1
length = len(arr)
while step < length:
for i in range(0, length, 2 * step):
left = arr[i:i + step]
right = arr[i + step:i + 2 * step]
merged = merge(left, right)
# Place the merged array back into the original array
for j, val in enumerate(merged):
arr[i + j] = val
step *= 2 # Double the sub-array length for the next iteration
return arr
unsortedArr = [3, 7, 6, -10, 15, 23.5, 55, -13]
sortedArr = mergeSort(unsortedArr)
print("Sorted array:", sortedArr)
The merge functions in the two Merge Sort implementations above are identical, as you may have noticed, but in the code directly above, the recursion is replaced with a while loop inside the mergeSort function. The code is a little more difficult to understand because the while loop splits and merges the array in situ.
In short, the while loop within the mergeThe merge function is used by the sort function to sort small portions (sub-arrays) of the original array using short step lengths. Larger portions of the array can then be merged and sorted by increasing the step length until the array is sorted in its entirety.
Merge Sort Time Complexity
See this article for a broad description of time complexity.
See this page for a more comprehensive and in-depth description of Merge Sort time complexity.
The Merge Sort’s temporal complexity is
O(n⋅logn)
Furthermore, the temporal complexity for various types of arrays is essentially the same. Whether the array is entirely shuffled or has previously been sorted, the algorithm must split it and then merge it back together.
The temporal complexity for Merge Sort is displayed in the graphic below.
Run the simulation below for different number of values in an array, and see how the number of operations Merge Sort needs on an array of nelements is O(nlogn):
------ IMAGE MUKAVI -----
The number of operations required for “Random,” “Descending,” and “Ascending” is nearly equal if we keep the number of values, n, unchanged.
Because the array is divided and then merged using comparison, whether or not the array has already been sorted, merge sort operates nearly consistently every time.
