Merge Sort

Like QuickSort, Merge Sort also follows the divide and conquer paradigm. It divides the input array into two halves recursively, sorts the smaller arrays and then merges them back together.

GeeksForGeeks: Merge Sort Example

In the example shown in the image above the array is first recursively divided into 2 halves until an array of 1 element each is not achieved, then these small arrays are merged back together in a sorted order to achieve the required sorted array.

Algorithm:

The algorithm takes use of 2 functions:

1. merge(arr, low, mid, high)

This is the heart of the merge sort algorithm. It assumes that arr[low...mid] and arr[mid+1...high] are sorted and merges them together into a sorted array of size arr[low...high].

Merging is simple, traverse both the arrays, compare both the elements of the arrays and insert the smaller element in the sorted sequence, increment the index of that array.

For example:

let arr = [3, 27, 38, 43, 9, 10, 82]
low = 0, mid = 3, high = 6

We can visualise arr[low...mid] and arr[mid+1...high] as 2 separate arrays

arr1 and arr2 respectively

arr1 = [3, 27, 38, 43] and arr2 = [9, 10, 82]
Let the array to store the sorted result be named as result =[low...high]
Let i = 0 be used for indexing of arr1[]
and j = 0 be used for indexing of arr2[]
and k = 0 be used for indexing of result[]

1.  arr[i] < arr[j]: // 3 < 9
        result[k] = arr[i]
        i = i + 1
        k = k + 1
        
    after 1st iteration result = [3]

2.  arr[i] > arr[j]: // 27 > 9
        result[k] = arr[j]
        j = j + 1
        k = k + 1
    
    after 2nd iteration result = [3, 9]

3.  arr[i] > arr[j]: // 27 > 10
        result[k] = arr[j]
        j = j + 1
        k = k + 1
        
    after 3rd iteration result = [3, 9, 10]
        
4.  arr[i] < arr[j]: // 27 < 82
        result[k] = arr[i]
        i = i + 1
        k = k + 1

    after 4th iteration result = [3, 9, 10, 27]

5.  arr[i] < arr[j]: // 38 < 82
        result[k] = arr[i]
        i = i + 1
        k = k + 1

    after 5th iteration result = [3, 9, 10, 27, 38]

6.  arr[i] < arr[j]: // 43 < 82
        result[k] = arr[i]
        i = i + 1
        k = k + 1
    after 6th iteration result = [3, 9, 10, 27, 38, 43]

// copy the remaining elements of arr2 into result
7.  result[k] = arr2[j]
    
    result = [3, 9, 10, 27, 38, 82]

2. merge_sort(arr, low, high)

The merge sort recursively splits the array into two halves and calls the merge() function to get the resultant sorted array.

merge_sort(arr, low,  high)
If low < high
     1. Find the middle point to divide the array into two halves:  
             mid = (l+r)/2
     2. Call merge_sort for the first half:   
             Call merge_sort(arr, low, mid)
     3. Call merge_sort for the second half:
             Call merge_sort(arr, mid+1, high)
     4. Merge the two halves sorted in step 2 and 3:
             Call merge(arr, low, mid, high)

Code in Python:

# Program to perform merge sort on an array


def merge(arr, low, mid, high):
    n1 = mid - low + 1
    n2 = high - mid

    # create temporary arrays
    """
    arr = [0] * n is equivalent to:
    arr = [0, 0, 0, ..., 0]
    array of n zeros
    """
    arr1 = [0] * n1
    arr2 = [0] * n2

    # copy data of arr into arr1 and arr2
    for i in range(0, n1):
        arr1[i] = arr[low + i]

    for i in range(0, n2):
        arr2[i] = arr[mid + 1 + i]

    # initialize i, j to 0
    i = j = 0

    # initialize k to lower index
    k = low

    # merge the 2 arrays
    while i < n1 and j < n2:
        if arr1[i] < arr2[j]:
            arr[k] = arr1[i]
            i += 1
        else:
            arr[k] = arr2[j]
            j += 1
        k += 1

    # if elements left in arr1 copy them to arr
    while i < n1:
        arr[k] = arr1[i]
        i += 1
        k += 1

    # if elements left in arr2 copy them to arr
    while j < n2:
        arr[k] = arr2[j]
        j += 1
        k += 1


def merge_sort(arr, low, high):
    if low < high:
        # mid = int((low + high) / 2)
        mid = int(low + ((high - low) / 2))

        # call merge_sort on 2 halves
        merge_sort(arr, low, mid)
        merge_sort(arr, mid+1, high)

        # merge the two sorted halves
        merge(arr, low, mid, high)


arr = [5, 21, 7, 3, 4, 8, 9, 10, 100, 15]

print('Before merge sort:', arr)

# Call merge sort on arr
merge_sort(arr, 0, len(arr)-1)

print('After merge sort:', arr)
"""
Outputs:
Before merge sort: [5, 21, 7, 3, 4, 8, 9, 10, 100, 15]
After merge sort: [3, 4, 5, 7, 8, 9, 10, 15, 21, 100]
"""

Time Complexity:

The merge sort function divides the array into two almost equal halves on each recursive call.

The merge function does a traversal on the array[low...high] for the merging process, that is, O(n) work.

The recurrence equation for any recursive call can be written as:

T(n) = a * T(n/b) + f(n)

where,

a = number of recursive calls to itself

b = amount by which the input gets reduced

f(n) = amount of work done other than the recursion

Hence, the recurrence equation for merge sort can be written as:

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

By Master Theorem, we can find the time complexity of such recurrence equations.

T(n) = O(n log n) 

[for Best, Average, Worst Case]

Here is the code in C language: Merge Sort in C

--
Have any questions or suggestions? Post in the comments below!!

By,

Anubhav Shrimal