Merge Sort

The divide-and-conquer approach

Many useful algorithms are recursive in structure: to solve a given problem, they call themselves recursively one or more times to deal with closely related sub-problems.

These algorithms typically follow a divide-and-conquer approach: they break the problem into several subproblems that are similar to the original prob- lem but smaller in size, solve the subproblems recursively, and then combine these solutions to create a solution to the original problem.

Divide the problem into a number of subproblems that are smaller instances of the same problem.

Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner.

Combine the solutions to the subproblems into the solution for the original problem.

• Divide: Divide the n-element sequence to be sorted into two subsequences of n=2 elements each.

• Conquer: Sort the two subsequences recursively using merge sort.

• Combine: Merge the two sorted subsequences to produce the sorted answer.

MERGE_SORT: O(nlogn)

MERGE-SORT(A,p,r)
  if p < r               // Check for base case: O(1)
     q = floor((p+r)/2)  // Divide: O(1)
     MERGE-SORT(A,p,q)   // Conquer: T(n/2)
     MERGE-SORT(A,q+1,r) // Conquer: T(n/2)
     MERGE(A,p,q,r)      // Combine: O(n)

Running time:

$$T(n)=\left\{\begin{array}{cc}\Theta(1) & \text { if } n=1 \\ 2 T(n / 2)+\Theta(n) & \text { otherwise }\end{array}\right.$$

Therefore, $T(n)$ is $\Theta(nlogn)$

MERGE: O(n)

where n = r - p + 1 is the total number of elements being merged.

MERGE(A,p,q,r)
   n1 = q - p + 1  // length of the subarray A[p..q]
   n2 = r - q.     // length of the subarray A[q+1..r]
   let L[1..n1 + 1] and R[1..n2 + 1] be new arrays // Left and Right
   for i = 1 to n1
      L[i] = A[p + i - 1] // copy the subarray A[p..q] into L[1..n1]
   for j = 1 to n2
      R[j] = A[q + j] // copy the subarray A[q+1..r] into R[1..n2]
   L[n1 + 1] = inf // put the sentinels at the ends of the array L
   R[n2 + 1] = inf // put the sentinels at the ends of the array R
   i = 1
   j = 1
   for k = p to r
     if L[i] <= R[j]
        A[k] = L[i]
        i = i + 1
     else A[k] = R[j]
        j = j + 1

Example: Remove Duplicates

Pseudocode: This algorithm sorts the list of names, then scans through the sorted list to find unique names and move them to the front of the list.

A = MERGE_SORT(A)     // Sorting using subroutine from class
j = 1                 // Initialize new index for result subarray
for i = 2 to A.length
    if A[j] != A[i]
        j = j + 1     // Increment index to point to next memory space
        A[j] = A[i]
print A[1...j]        // Output only the required subarray