Merge Sort

• Divide and conquer method
• Split the array into halves and then merge those halves together

Implementation

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        // m is the point where the array
		// is divided into two subarrays
        int mid = left + (right - left) / 2;
 
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
 
        // Merge the sorted subarrays
        merge(arr, left, mid, right);
    }
}

• Merge Algorithm
  1. Access the first item from both sequences
  2. While not finished with either sequence
     1. Compare the current items from the two sequences
     2. Copy the smaller current item to the output sequence
     3. Access the next item from the input sequence whose item was copied
  3. Copy any remaining items from the first sequence to the output sequence
  4. Copy any remaining items form the second sequence to the output sequence

void merge(int arr[], int left, int mid, int right) {
    // Create X ← arr[left..mid] & Y ← arr[mid+1..right]
    int n1 = mid - left + 1;
    int n2 = right - mid;
 
    int X[n1], Y[n2];
 
    for (int i = 0; i < n1; i++)
        X[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        Y[j] = arr[mid + 1 + j];
 
    // Merge the arrays X and Y into arr
    int i, j, k;
    i = 0;
    j = 0;
    k = left;
    while (i < n1 && j < n2) {
        if (X[i] <= Y[j]) {
            arr[k] = X[i];
            i++;
        } else {
            arr[k] = Y[j];
            j++;
        }
        k++;
    }
    // When we run out of elements in either X or Y,
	// append the remaining elements
    while (i < n1) {
        arr[k] = X[i];
        i++;
        k++;
    }
 
    while (j < n2) {
        arr[k] = Y[j];
        j++;
        k++;
    }
}

Correctness

Claim

Mergesort sorts any list of $n$ elements.

Proof Base case: $n=1$ Inductive hypothesis: Assume true for $1,2,\dots ,n-1$ Inductive Step: TODO

Recurrence Relation

Definition

$T(n)$ = max number of compares to merge sort a list of length $n$

When:

$$T(n)=\{\begin{array}{ll}0& n=1\\ 2T\left(\frac{n}{2}\right)+n& n>1\end{array}$$

Claim

$T(n)=n{\log }_{2}n$

Proof: Base case: when $n=1$, $T(1)=0=n{\log }_{2}n$ Inductive hypotheses: assume $T(n)=n{\log }_{2}n$ Inductive step:

$$\begin{array}{rl}T(2n)& =2T(n)+2n\\ & =2n{\log }_{2}n+2n\\ & =2n({\log }_2(2n)-1)+2n\end{array}$$