Merge Sort

I. Concept and Introduction

Merge sort is an efficient, stable sorting algorithm based on the merge operation. It is a typical application of the divide-and-conquer method. It combines existing sorted subsequences to obtain a fully sorted sequence; that is, it first sorts each subsequence and then sorts the subsequences between them. If two sorted lists are merged into one sorted list, it is called two-way merge.

II. Applicability

When there are n records, logn rounds of merge sort are required, and in each round of merging, the number of comparisons does not exceed n, and the number of element movements is n. Therefore, the time complexity of merge sort is O(nlogn). Merge sort requires storage space equal to the number of records to be sorted, so the space complexity is O(n).

Merge sort is suitable for scenarios with large data volumes and requirements for stability.

III. Process Illustration

Merge sort is an example of a recursive algorithm. The basic operation of this algorithm is to merge two sorted arrays. Take two input arrays A and B, an output array C, and three counters i, j, k, which are initially positioned at the start of their respective arrays.

The smaller of A[i] and B[j] is copied to the next position in C, and the relevant counter is advanced by one.

When one of the input arrays is exhausted, the remaining part of the other array is copied to C.

Top-down merge sort, recursive grouping illustration:

Merge sort on pairs of data in the third row.

Merge sort on groups of four data in the second row.

Overall merge sort.

IV. Java Example Code

Source Code Download: Download

MergeSort.java File Code:

public class MergeSort {

    // Merge two parts of arr[l...mid] and arr[mid+1...r]
    private static void merge(Comparable[] arr, int l, int mid, int r) {

        Comparable[] aux = Arrays.copyOfRange(arr, l, r + 1);

        // Initialize, i points to the start index of the left half; j points to the start index of the right half
        int i = l, j = mid + 1;
        for (int k = l; k <= r; k++) {

            if (i > mid) {  // If all elements in the left half have been processed
                arr[k] = aux[j - l];
                j++;
            } else if (j > r) {   // If all elements in the right half have been processed
                arr[k] = aux[i - l];
                i++;
            } else if (aux[i - l].compareTo(aux[j - l]) < 0) {  // Left half element < Right half element
                arr[k] = aux[i - l];
                i++;
            } else {  // Left half element >= Right half element
                arr[k] = aux[j - l];
                j++;
            }
        }
    }

    // Recursively use merge sort to sort the range of arr[l...r]
    private static void sort(Comparable[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = (l + r) / 2;
        sort(arr, l, mid);
        sort(arr, mid + 1, r);
        // For arr[mid] <= arr[mid+1], do not merge
        // This is very effective for nearly sorted arrays, but has some performance loss for general cases
        if (arr[mid].compareTo(arr[mid + 1]) > 0)
            merge(arr, l, mid, r);
    }

    public static void sort(Comparable[] arr) {

        int n = arr.length;

sort(arr, 0, n - 1);
}

// Test MergeSort
public static void main(String[] args) {

    int N = 1000;
    Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
    sort(arr);
    // Print array
    SortTestHelper.printArray(arr);
}