Merge Sort

Merge sort (English: Merge sort, or mergesort) is an efficient sorting algorithm based on the merge operation.

Merge sort is a very typical application of the divide-and-conquer (Divide and Conquer) approach. It merges already ordered subsequences to obtain a fully ordered sequence; that is, first make each subsequence ordered, then make the segments between subsequences ordered. Merging two ordered lists into one ordered list is called a two-way merge.

Imagine you need to sort a completely shuffled deck of playing cards. An efficient way is: first split the deck into two smaller piles, sort each pile separately, and finally merge these two ordered piles into one fully ordered deck.Merge SortIt is precisely based on thisDivide and conquerThe classic sorting algorithm of thought.

Its core operations can be summarized in two steps:

  • Divide: Recursively split a large unordered list from the middle over and over, decomposing it into many small sublists, until each sublist contains only one element (a list of one element is naturally ordered).
  • Conquer: Recursively merge these ordered sublists pairwise, sorting during the merging process, and finally merge them into one complete ordered list.

Applicability

Merge sort is suitable for scenarios with large amounts of data and where stability is required.

Merge sort is a stable sorting algorithm (that is, the relative order of equal elements remains unchanged after sorting). Its time complexity is O(n log n) in all cases, which makes it very efficient when processing large-scale data, but its space complexity is O(n), because the merging process requires extra arrays to temporarily store data.

The following flowchart clearly shows the entire process of divide and conquer in merge sort:

Process Diagram

Merge sort is an example of a recursive algorithm. The basic operation in this algorithm is merging two sorted arrays: it takes two input arrays A and B, an output array C, and three counters i, j, k, which are initially positioned at the beginnings of their corresponding arrays.

The smaller of A[i] and B[j] is copied to the next position in C, and the corresponding counter advances one step.

When one of the two input arrays is exhausted, copy the remaining part of the other array into C.

Top-down merge sort, recursive grouping diagram:

Perform merge sort on the data in the third row, grouped in pairs.

Perform merge sort on the data in the second row, grouped in fours.

Overall merge sort

Java example code

Source code package download:Download

MergeSort.java file code:

public class MergeSort {

    // Merge the two parts 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 starting index l of the left half; j points to the starting index mid+1 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) {  // The element pointed to in the left half < the element pointed to in the right half
                arr[k] = aux[i - l];
                i++;
            } else {  // The element pointed to in the left half >= the element pointed to in the right half
                arr[k] = aux[j - l];
                j++;
            }
        }
    }

    // Recursively use merge sort to sort the range 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 the case where arr[mid] <= arr[mid+1], skip the merge
        // This is very effective for nearly ordered arrays, but for general cases, there is a certain performance loss
        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);
    }
}

Algorithm principles and detailed steps

The implementation of merge sort mainly relies on two core functions:merge_sort(responsible for the "divide") andmerge(responsible for "governance").

1. Decomposition functionmerge_sort

This function works recursively:

Base case: If the current array length is less than or equal to 1, then it is already ordered, return directly.

Recursive case：

  • Find the middle position of the arraymid。
  • For the left halfarr[:mid]Recursive callmerge_sort。
  • For the right halfarr[mid:]Recursive callmerge_sort。
  • Finally, callmergeThe function merges the already sorted left and right parts.

2. Merge functionmerge

This is the essence of the algorithm, responsible for merging twoAlready sortedsmall arrays into one large ordered array. The process is similar to flipping through two phone books already sorted alphabetically and merging them into one.

  1. Create a temporary arraytemp, and three pointers:i(pointing to the current element of the left array),j(pointing to the current element of the right array),k(pointing to the fill position of the temporary array).
  2. Compareleft[i]andright[j], thenthe smallerput that element intotemp[k], then the corresponding pointer andkMove forward one step.
  3. Repeat step 2 until all elements of one of the arrays have been placed into the temporary array.
  4. Append all the remaining elements from the other array (which are inherently larger than the already placed elements and are already ordered) directly to the end of the temporary array in order.
  5. the temporary arraytempThe ordered sequence in ... is copied back to the corresponding positions of the original array.

Code implementation and line-by-line analysis

Let's implement merge sort in Python. We will provide a complete, thoroughly commented version.

Test data

First, let's prepare an unordered list as test data:

Example

# Test data: an unordered list of integers
test_array = [38, 27, 43, 3, 9, 82, 10]
print("Original array:", test_array)

Complete implementation

Example

def merge_sort(arr):
    """
The main function for merge sort.
Parameters:
arr (list): The list to be sorted.
Returns:
list: the new sorted list (for clarity, this implementation returns a new list).
    """
    # Base case: if the array length is 0 or 1, it is already sorted
    if len(arr) <= 1:
        return arr

    # 1. Divide: find the midpoint and split the array into two halves
    mid = len(arr) // 2
    left_half = arr[:mid]  # Left half
    right_half = arr[mid:] # Right half

    # Recursively sort the left and right halves
    left_sorted = merge_sort(left_half)
    right_sorted = merge_sort(right_half)

    # 2. Conquer: merge the two sorted subarrays
    return merge(left_sorted, right_sorted)


def merge(left, right):
    """
Merge two sorted lists.
Parameters:
left (list): The first sorted list.
right (list): The second sorted list.
Returns:
list: The merged sorted list.
    """
    sorted_list = []  # Temporary list to store the merge result
    i = j = 0         # i and j are pointers traversing left and right, respectively

    # 3. Compare and merge: while both lists still have elements
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  # Note: use <= to maintain sort stability
            sorted_list.append(left[i])
            i += 1
        else:
            sorted_list.append(right[j])
            j += 1

    # 4. Handle remaining elements: append all remaining elements from the left or right list to the result
    # Since left and right are already sorted, the remaining elements must all be larger than the already merged elements
    sorted_list.extend(left[i:])
    sorted_list.extend(right[j:])

    return sorted_list


# Run the algorithm with test data
sorted_array = merge_sort(test_array.copy())  # Use copy to avoid modifying the original array
print("After merge sort:", sorted_array)

Code execution and output

When you run the above code, you will see the following output:

原始数组: [38, 27, 43, 3, 9, 82, 10]
归并排序后: [3, 9, 10, 27, 38, 43, 82]

Algorithm complexity analysis

Understanding the efficiency of an algorithm is crucial. We summarize the performance of merge sort through the table below:

Metric Complexity Description
Time complexity O(n log n) This is the most significant advantage of merge sort.log nIt comes from the number of recursion levels (splitting the array in half),nIt comes from each level of merging operations needing to traverse all elements. Regardless of the initial state of the data (best, worst, average case), the time complexity is O(n log n).
Space complexity O(n) The merging process requires extra space equal in size to the original array to store temporary arrays. This is the main disadvantage of merge sort.
Stability Stable InmergeIn the function, whenleft[i] == right[j]When this happens, we prioritize takingleft[i](using<=comparison), which ensures that the original relative order of equal elements remains unchanged.
Whether it is in-place sorting no It requires additional memory space.

More code demonstrations

other extensions