Merge Sort

Overview#

  • Time Complexity: O(nlogn) in all scenarios
  • Space Complexity: O(n + log(n)) simplified to O(n)
  • Not In-Place
  • Stable

General Idea#

Merge sort is a divide and conquer technique. Given an array, we repeatedly divide it into 2 arrays, till we have one element of concern. At the point, that single element will be sorted.

Now, we proceed to merge the divided sections of the array. When merging, we create a temporary array to hold the items from the 2 arrays we are merging. We will have 2 pointers i and j to track the current index of array 1 and array 2. In each iteration, we compare the index pointed to by the pointer i in array 1 to that of the index of array 2 by pointer j. Whichever element is the smaller one, we copy that into the temporary array.

At the end of the merge process, there maybe left over elements in either array, so we just copy them over into the temporary array. At the end of the merge process, we would have merged both arrays into one sorted array.

Now, we need to copy whatever elements are in the temporary array back into the original array starting from index i.

Time Complexity#

Time taken to merge 2 portions of the array will be O(n).

Let mergeSort take a time complexity of T(n). Due to the 2 calls to mergeSort for the 2 halves of the array and subsequently to merge function which takes O(n), T(n) can be represented as follows:

T(n) = 2 * T(n/2) + O(n)

For every call to merge(), there will be a time complexity of O(n). We are making log(n) such calls due to the depth of the recursive call stack.

Therefore, T(n) simplifies to an order of O(nlogn).

Note: There is no best/worst case for merge sort. Therefore, despite the initial condition of the list, already sorted, reverse sorted etc., merge sort will still take the same time complexity of O(nlogn).

Reference: https://www.youtube.com/watch?v=sfmaf4QpVTw&t=104s

Space Complexity#

Note that merge sort is not an in-place sort, which means it requires extra space. This extra space is required in the merge algorithm where we need to copy the elements from the original array into a temporary array. This takes O(n) space.

Apart from a temporary, we also need to consider the recursion stack involved. Note that thought each call to mergeSort has 3 sub-functions, not all the recursive calls occur simultaneously. Since it is a divide and conquer algorithm, we need ceil(log(n)) + 1, which simplifies to O(log(n)) space for the stack.

The total space complexity is therefore given by O(n + log(n)) which is dominated by the O(n) term, and hence simplifies to O(n).

Implementation#

def merge_sort(arr, i=None, j=None):
print(i, j)
if(i is None or j is None):
merge_sort(arr, 0, len(arr) - 1)
elif(i < j):
mid = (i+j) // 2
merge_sort(arr, i, mid)
merge_sort(arr, mid + 1, j)
merge(arr, i, mid, j)
def merge(arr, i, mid, j):
temp = [None] * (j-i+1)
# left keeps track of left subarray, right keeps track of right subarray
# i keeps track of current position in temp array
left, right, curr = i, mid + 1, 0
while(left <= mid and right <= j):
if(arr[left] < arr[right]):
temp[curr] = arr[left]
left += 1
else:
temp[curr] = arr[right]
right += 1
curr += 1
# copy any remaining elements into temp
while(left <= mid):
temp[curr] = arr[left]
curr += 1
left += 1
while(right <= j):
temp[curr] = arr[right]
curr += 1
right += 1
# copy temp into original array
for k in range(len(temp)):
arr[i+k] = temp[k]
return arr
arr = [9,8,7,6,5,4,3,2,1]
merge_sort(arr)
print(arr)