Merge Sort

Merge sort is a popular sorting algorithm which uses divide and conquer algorithm. Consider an array A to be sorted. We divide the array A into two parts and sort them individually. The heart of the Merge Sort is a procedure called Merge. Let’s see the Merge procedure first and then we will use Merge as a subroutine to implement Merge Sort algorithm.

Merge Procedure

Here sub-array_1 A[p,q] and sub-array-2 A[q+1,r] are sorted individually and we want to sort them as a whole.

• Len1 = q-p+1 and Len2 = r-q
• Create two separate lists of sizes of Len1+1 and Len2+1
• Copy the two sorted part of the arrays into the lists
• Add infinity to the end of both lists (the maximum number the data structure can support)
• Take 3 pointers i, j, k where i & j point to first elements of both the lists and k points to the first element of the original array A

• Now we will fill the array A(basically overwrite) in a sorted manner.
• Compare the elements at i and j. Whichever is smaller (say i), copy its value to kth index in array A and then increment pointers k and i (we considered ele(i) <ele(j)).
• We repeat the above process till k does not reach the end of the array A.
• Compare (1,2) and then increment i and k
• Compare (5,2) and then increment j and k
• Compare (5,4) and then increment j and k
• Compare (5,6) and then increment i and k
• Compare (7,6) and then increment j and k
• Compare (7,9) and then increment i and k
• Compare (8,9) and then increment i and k
• Compare (inf,9) and then increment j and k
• Thus by the end of the Merge procedure the two individually sorted sub_array gets sorted as a whole in the original array A

Psuedo code for Merge Sort procedure

Merge(A, p, q, r) {
    // Consider all arrays as 1-indexed arrays
    n1 = q - p + 1
    n2 = r - p
    let Left[1.......n1 + 1] and Right[1.........n2 + 1] be two new arrays
    for (i = 1 to n1) // to copy the first sorted list into array Left "O(N / 2)"
    {
        Left[i] = A[p + i - 1]                          
    }
    for (j = 1 to n2) // to copy the second sorted list into array Right "O(N / 2)"
    {
        Right[i] = A[q + j]                             
    }
    Left[n1 + 1] = inf
    Right[n2 + 1] = inf
    i = 1, j = 1
    for (k = p to r) { // "O(N / 2)"
        if (Left[i] <= Right[j]) {
            A[k] = Left[j]
            i++
        }
        else {
            A[k] = Right[j]
            j++
        }
        k++
    }
}

Time complexity of merge procedure

time taken = O(n/2 + n/2 + n) = O(n)

Space complexity of merge procedure:

extra space = O(n/2 + n/2) // for two extra arrays Left and Right = O(n)
Now, we have an array A consisting on n elements. Let T(n) be the time required to sort the array.

Psuedo code for Merge sort

Merge_sort(A, p, r) {
    if (p < r) {
        q = floor((p + r) / 2)  // find the mid point
        Merge_sort(A, p, q)     // T(n / 2)
        Merge_sort(A, q + 1, r) // T(n / 2)
        Merge(A, p, q, r)       // T(n)
    }
}

Time complexity of merge sort

T(n) = time taken to sort n sized array
We divided the array into two n/2 sized array and sorted them individually.
So, time taken to sort those two sub arrays = T(n/2) + T(n/2) = 2T(n/2)
Merging the two arrays of size n/2 into an array of size n requires calling of the merge procedure which requires a time of O(n)
So, we come to the following recursive equation: T(n) = 2*T(n/2) + O(n)
Using Master’s theorem, we get T(n) = O(n.logn)

Recursive tree

• Consider an array with 6 elements. The array is 1-indexed, thus p=1 and r=6. Let MS represent the Merge_sort function and Merge as usual represents our Merge function.
• We see that the total number of function call here is 16.
• The height of the tree is floor(log2n) + 1. Substitute n = 6, we get four levels as shown

Space complexity of merge sort

• We don’t consider the space required for variables p, q, r, i, j as they require constant space. The input array is already given. Thus, it is not considered in the extra space required category.
• The procedure Merge requires two new lists of size n/2 every time it is called on an array of size n. Instead of creating two list space every time, we can use as a global array of O(n) space for copying of elements. It can be used by every call to procedure Merge one by one.
  (1) Thus space required for Merge is O(n)
• The other extra space used during merge sort is the stack space for recursive function calls. Now in our example, for n=6, the number of function calls was 16
• But, do we really need a stack with 16 activation records entries? Turns out, we don’t really need a stack of height 16.

• All the function calls in the same level in the recursion tree ocuupy the same cell of the stack. Thus we have a stack of height equal to the height of the tree.
  Height of stack = Height of the recursive tree

  • For n sized array
  • Number of levels = floor(log2n) + 1
  • Assume each cell of stack( Activation record) is ok size k.
    
  • (2) Stack Size = (floor(log2n) + 1)*k = O(k*log2n) = O(log2n)
  • From (1) and (2)
  • Space Complexity = n + log2n = O(n)

Note

• Merge sort falls under the category of out-of-place sorting algorithm since we need extra space for sorting (extra space is needed in the merge procedure, thus it is not in-place)
• Merge sort is a stable sorting algorithm as the algorithm used in our pseudo code doesn’t change the relative position of same valued elements