Merge Sort
G
w
A
s
L
C
S
A
from __future__ import annotations
def merge(left_half: list, right_half: list) -> list:
"""Helper function for mergesort.
>>> left_half = [-2]
>>> right_half = [-1]
>>> merge(left_half, right_half)
[-2, -1]
>>> left_half = [1,2,3]
>>> right_half = [4,5,6]
>>> merge(left_half, right_half)
[1, 2, 3, 4, 5, 6]
>>> left_half = [-2]
>>> right_half = [-1]
>>> merge(left_half, right_half)
[-2, -1]
>>> left_half = [12, 15]
>>> right_half = [13, 14]
>>> merge(left_half, right_half)
[12, 13, 14, 15]
>>> left_half = []
>>> right_half = []
>>> merge(left_half, right_half)
[]
"""
sorted_array = [None] * (len(right_half) + len(left_half))
pointer1 = 0 # pointer to current index for left Half
pointer2 = 0 # pointer to current index for the right Half
index = 0 # pointer to current index for the sorted array Half
while pointer1 < len(left_half) and pointer2 < len(right_half):
if left_half[pointer1] < right_half[pointer2]:
sorted_array[index] = left_half[pointer1]
pointer1 += 1
index += 1
else:
sorted_array[index] = right_half[pointer2]
pointer2 += 1
index += 1
while pointer1 < len(left_half):
sorted_array[index] = left_half[pointer1]
pointer1 += 1
index += 1
while pointer2 < len(right_half):
sorted_array[index] = right_half[pointer2]
pointer2 += 1
index += 1
return sorted_array
def merge_sort(array: list) -> list:
"""Returns a list of sorted array elements using merge sort.
>>> from random import shuffle
>>> array = [-2, 3, -10, 11, 99, 100000, 100, -200]
>>> shuffle(array)
>>> merge_sort(array)
[-200, -10, -2, 3, 11, 99, 100, 100000]
>>> shuffle(array)
>>> merge_sort(array)
[-200, -10, -2, 3, 11, 99, 100, 100000]
>>> array = [-200]
>>> merge_sort(array)
[-200]
>>> array = [-2, 3, -10, 11, 99, 100000, 100, -200]
>>> shuffle(array)
>>> sorted(array) == merge_sort(array)
True
>>> array = [-2]
>>> merge_sort(array)
[-2]
>>> array = []
>>> merge_sort(array)
[]
>>> array = [10000000, 1, -1111111111, 101111111112, 9000002]
>>> sorted(array) == merge_sort(array)
True
"""
if len(array) <= 1:
return array
# the actual formula to calculate the middle element = left + (right - left) // 2
# this avoids integer overflow in case of large N
middle = 0 + (len(array) - 0) // 2
# Split the array into halves till the array length becomes equal to One
# merge the arrays of single length returned by mergeSort function and
# pass them into the merge arrays function which merges the array
left_half = array[:middle]
right_half = array[middle:]
return merge(merge_sort(left_half), merge_sort(right_half))
if __name__ == "__main__":
import doctest
doctest.testmod()
About this Algorithm
Problem Statement
Given an array of n elements, write a function to sort the array
Approach
- Find a mid point and divide the array into to halves based on the mid point
- Recursively call the merge sort function for both the halves
- Merge the two sorted halves to get the sorted array
Time Complexity
Best case - O(n log n)
Average - O(n log n)
Worst case - O(n log n)
Space Complexity
O(n)
Example 1
arr = [1, 3, 9, 5, 0, 2]
Divide the array in two halves [1, 3, 9] and [5, 0, 2]
Recursively call merge sort function for both these halves which will provide sorted halves
=> [1, 3, 9] & [0, 2, 5]
Now merge both these halves to get the sorted array [0, 1, 2, 3, 5, 9]
Example 2
arr = [1, 9, 2, 5, 7, 3, 6, 4]
Divide the array into two halves [1, 9, 2, 5] and [7, 3, 6, 4]
As you can see that the above two halves are not yet sorted, so divide both of them into two halves again.
This time we get four arrays as [1, 9], [2, 5], [7, 3] and [6, 4].
We see that the last two arrays are again not sorted, so we divide them again into two halves and we will get [7], [3], [6], and [4].
Since an array of a single element is sorted, we now have all the arrays sorted, now we only need to merge them appropriately.
First, the arrays of one element will be merged as they were divided in last, and are at top of the recursion stack, so we get [3,7] and [4,6].
Now the merge will occur accordingly to the recursion stack, [1, 9] and [2, 5] will be merged and will make [1, 2, 5, 9].
Similarly [3, 7] and [4, 6] will be merged and made [3, 4, 6, 7].
At the next stack level [1, 2, 5, 9] and [3, 4, 6, 7] will be merged and we will get the final sorted array as [1, 2, 3, 4, 5, 6, 7, 9].
