Merge Sort

Merge Sort: Introduction

The idea of merge sort is to divide the array into two halves and then merge them in a sorted manner. The merge sort is a recursive algorithm. The base case is when the array has only one element. The recursive step is to divide the array into two halves and then merge them in a sorted manner. The merge step is to compare the elements from left and right sub-arrays and then put the smaller element in the sorted array. The merge step is repeated until the two sub-arrays are empty.

Merge Sort: Implementation

def merge(array1, array2):
    combined = []
    i = 0
    j = 0
    while i < len(array1) and j < len(array2):
        if array1[i] < array2[j]:
            combined.append(array1[i])
            i += 1
        else:
            combined.append(array2[j])
            j += 1         
    while i < len(array1):
        combined.append(array1[i])
        i += 1
    while j < len(array2):
        combined.append(array2[j])
        j += 1
    return combined

def merge_sort(my_list):
    if len(my_list) == 1:
        return my_list
    mid = int(len(my_list)/2)
    left = my_list[:mid]
    right = my_list[mid:]
    return merge(merge_sort(left), merge_sort(right))

print(merge_sort([3,1,4,2]))

Merge Sort: Big O

The time complexity of merge sort is O(n log n). It is the most efficient sorting algorithm. The space complexity is O(n).