Merge Sort

Intro:

Merge sort is a simple array sorting algorithm. It works by dividing the array into two parts and sorting them recursively. The array is divided into two parts until it is of size 1. Then the two parts are merged. The merge step is done by comparing the first element of each part and inserting the smaller element into the sorted array. The merge step is repeated until the array is sorted.

merge_sort.png

Pseudocode:

ALGORITHM Mergesort(arr)
    DECLARE n <-- arr.length

    if n > 1
      DECLARE mid <-- n/2
      DECLARE left <-- arr[0...mid]
      DECLARE right <-- arr[mid...n]
      // sort the left side
      Mergesort(left)
      // sort the right side
      Mergesort(right)
      // merge the sorted left and right sides together
      Merge(left, right, arr)

ALGORITHM Merge(left, right, arr)
    DECLARE i <-- 0
    DECLARE j <-- 0
    DECLARE k <-- 0

    while i < left.length && j < right.length
        if left[i] <= right[j]
            arr[k] <-- left[i]
            i <-- i + 1
        else
            arr[k] <-- right[j]
            j <-- j + 1

        k <-- k + 1

    if i = left.length
       set remaining entries in arr to remaining values in right
    else
       set remaining entries in arr to remaining values in left

Trace:

Sample Array:

[8, 4, 23, 42, 16, 15]

Step 1:

Split the array into two halves.

arr [8, 4, 23, 42, 16, 15]
left [8, 4, 23]
right [42, 16, 15]

Step 2:

Split the left into two halves.

arr [8, 4, 23]
left [8]
right [4, 23]

Step 3:

The resultant left is one element, so, split the right into two halves.

arr [4, 23]
left [4]
right [23]

Step 4:

Now, all elements in the original left are single elements. Merge the last two halves by copying elements decently.

merged [4, 23]

Step 5:

Merge in a sorted order the recently merged with the single element in their level.

merged [4, 8, 23]

Step 6:

Now, the original left is sorted and merged. Split the original right into two halves.

arr [42, 16, 15]
left [42]
right [16, 15]

Step 7:

The resultant left is one element, so, split the right into two halves.

arr [16, 15]
left [16]
right [15]

Step 8:

Now, all elements in the original right are single elements. Merge the last two halves by copying elements decently.

merged [15, 16]

Step 9:

Merge in a sorted order the recently merged with the single element in their level.

merged [15, 16, 42]

Step 10:

Now, both the original right and original right are sorted and merged. Merge in a sorted order the original left and original right.

merged [4, 8, 15, 16, 23, 42]

Result

[4, 8, 15, 16, 23, 42]

Efficiency:

Time Complexity: O(n * log n): It has recursion.

Space Complexity: O(n): copying process needs space