Merge Sort

Algorithm:

• Iteratively Divide the list to two halves
• Sort and Merge the divided list until one list remains recursively

Time Complexity:

• Best/Worst/Average: O(nlogn) -list is divided into two halves and it takes linear time to merge the list back.

Space Complexity:

• O(n) - usually no extra space is required

In-place: yes
Stable: yes

Python Implementation

def merge_sort(arr):
    m = len(arr)/2
    L = arr[:m]
    R = arr[m:]
    merge_sort(L)
    merge_sort(R)
    i = j = k = 0
   while i < len(L) and j < len(R):
       if L[i] < R[j]:
            arr[k] = L[i]
            i += 1
       else:
             arr[k] = R[j]
             j += 1
       k += 1
     
    while i < len(L):
           arr[k] = L[i]
           i += 1
           k += 1
    while j< len[R]:
           arr[k] = R[j]
           j += 1
           k += 1