Merge Sort

Merge sort is a divide-and-conquer sorting algorithm that divides the input array into two halves, recursively sorts each half, and then merges the sorted halves back together. The algorithm is stable and has a time complexity of $O(N\log N)$.

Features

• Stable sorting algorithm
• In-place sorting algorithm

Implementation

Pseudocode

procedure mergeSort(A : list of sortable items)
    if length(A) > 1 then
        mid = length(A) / 2
        left = A[0 : mid]
        right = A[mid : length(A)]
        mergeSort(left)
        mergeSort(right)
        merge(A, left, right)
    end if
end procedure

procedure merge(A : list of sortable items, left : list of sortable items, right : list of sortable items)
    i = 0
    j = 0
    k = 0
    while i < length(left) and j < length(right) do
        if left[i] <= right[j] then
            A[k] = left[i]
            i = i + 1
        else
            A[k] = right[j]
            j = j + 1
        end if
        k = k + 1
    end while
    while i < length(left) do
        A[k] = left[i]
        i = i + 1
        k = k + 1
    end while
    while j < length(right) do
        A[k] = right[j]
        j = j + 1
        k = k + 1
    end while
end procedure

Java

public static void mergeSort(int[] arr) {
    if (arr.length > 1) {
        int mid = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);
        mergeSort(left);
        mergeSort(right);
        merge(arr, left, right);
    }
}

public static void merge(int[] arr, int[] left, int[] right) {
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            arr[k] = left[i];
            i++;
        } else {
            arr[k] = right[j];
            j++;
        }
        k++;
    }
    while (i < left.length) {
        arr[k] = left[i];
        i++;
        k++;
    }
    while (j < right.length) {
        arr[k] = right[j];
        j++;
        k++;
    }
}

Runtime Analysis

Given $N$ elements in the array, the time complexity of merge sort is $\Theta (N\log N)$.

Best Case

The best case occurs when the array is already sorted. In this case, the algorithm makes $\log N$ passes through the array, each of which takes $O(N)$ time to merge the subarrays. The time complexity is $\Omega (N\log N)$.

Worst Case

The worst case occurs when the array is sorted in reverse order. In this case, the algorithm makes $\log N$ passes through the array, each of which takes $O(N)$ time to merge the subarrays. The time complexity is $O(N\log N)$.

Source

The existing course note was retained and normalized during the merge.

Related: Topic index.