Merge Sort

Merge sort is similar to quick sort as it makes use of recursion and Divide and Conquer technique. It complexity is O(n log n) as the pivot point is always in the middle.

The main idea behind merge sort is to keep breaking down the problem until we reach such small units that by the nature of them the sorting is done for them. The on our way back up we sort the items step by step, by the time when we reach the top of the call, our container is sorted.

Let’s take a really simple example of an array with 3 items in it: [ 2, 1, 0]

Step 1: find a middle point and break it in two parts: [2] and [1, 0]

Step 2: first part contains only one item, so by the definition it is already sorted. Second part contains two items, so find a middle point and break it in two parts: [1] and [0]

Step 3: [1] and [0] both contain one item each, so they are sorted by definition. As whole array is broken down into the smallest units possible, now we start merging them back. 0 is smaller than 1 so we copy 0 and then 1 into a new array, which we call “sorted_array”. sorted_array = [0, 1]

Step 4: now we are left with sorted array [2] and new sorted_array. So there is nothing else to do but to copy 2 into our sorted_array = [0, 1, 2].

At this point we have sorted our array.

Pseudo code for our merge sort:

function merge_sort(array_to_sort)
    if length of array_to_sort less is max 1
        return array_to_sort
    left = merge_sort(left half of array_to_sort)
    right = merge_sort(right half of array_to_sort)
    return merge_sides(left, right)

Possible implementation in python:

def merge_sides(left, right):
    index_left = 0
    index_right = 0
    merged = []

    while index_left < len(left) and index_right < len(right):
        if left[index_left] < right[index_right]:
            merged.append(left[index_left])
            index_left += 1
        else:
            merged.append(right[index_right])
            index_right += 1

    if len(left) > 0:
        merged.extend(left[index_left:])
    if len(right) > 0:
        merged.extend(right[index_right:])

    return merged
    
def merge_sort(array_to_sort):
    if len(array_to_sort) <= 1:
        return array_to_sort
    middle = len(array_to_sort) // 2
    left=merge_sort(array_to_sort[:middle])
    right=merge_sort(array_to_sort[middle:])

    return merge_sides(left, right)