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 algorithm. It merges already sorted subsequences to obtain a completely sorted sequence; that is, it first makes each subsequence sorted, and then makes the segments between subsequences sorted. Merging two sorted tables into one sorted table is called two-way merge.

Imagine you need to sort a completely shuffled deck of cards. An efficient method is: first divide the deck into two small piles, sort each small pile separately, and finally merge these two sorted piles into one complete sorted deck. Merge sort is a classic sorting algorithm based on this divide-and-conquer idea.

Its core operation can be summarized in two steps:

• Divide: Recursively split a large unsorted list from the middle into several smaller sublists until each sublist contains only one element (a list with one element is naturally sorted).
• Conquer: Recursively merge these sorted sublists in pairs, sorting during the merge process, and finally merging them into a complete sorted list.

Applicable Scenarios

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

Merge sort is a stable sorting algorithm (i.e., the relative order of equal elements remains unchanged after sorting). Its time complexity is O(n log n) in any case, making it very efficient for processing large-scale data. However, its space complexity is O(n) because the merge process requires additional arrays to temporarily store data.

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

Process Illustration

Merge sort is an instance of a recursive algorithm. The basic operation in this algorithm is merging two sorted arrays. Take two input arrays A and B, one output array C, and three counters i, j, k, initially positioned at the beginning of their respective arrays.

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

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:

Perform merge sort on the data in groups of two in the third row

Perform merge sort on the data in groups of four in the second row

Perform merge sort on the entire set

Java Example Code

Source 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= aux;

                j++;

            }else if(j > r){// If all elements in the right half have been processed

                arr= aux;

                i++;

            }else if(aux.compareTo(aux)<0){// The element pointed to by the left half < The element pointed to by the right half

                arr= aux;

                i++;

            }else{// The element pointed to by the left half >= The element pointed to by the right half

                arr= aux;

                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 cases where arr <= arr[mid+1], do not perform merge

        // Very effective for nearly sorted arrays, but has some performance loss in general cases

        if(arr.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 Principle and Detailed Steps

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

1. Decomposition Function merge_sort

This function works recursively:

Base Case: If the length of the current array is less than or equal to 1, it is already sorted, so return directly.

Recursive Case:

• Find the middle position mid of the array.
• Recursively call merge_sort on the left half arr[:mid].
• Recursively call merge_sort on the right half arr[mid:].
• Finally, call the merge function to merge the already sorted left and right halves.

2. Merge Function merge

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

1. Create a temporary array temp, 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 filling position of the temporary array).
2. Compare left and right, put the smaller element into temp, then advance the corresponding pointer and k by one step.
3. Repeat step 2 until all elements of one array have been placed into the temporary array.
4. Directly append all remaining elements from the other array (they are inherently larger than the elements already placed and are already sorted) to the end of the temporary array in order.
5. Copy the sorted sequence from the temporary array temp back to the corresponding positions in the original array.

---

Code Implementation and Line-by-Line Analysis

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

Test Data

First, we prepare an unsorted list as test data:

Example

# Test data: an unsorted integer list

test_array =[38,27,43,3,9,82,10]

print("Original array:", test_array)

Complete Implementation

Example

def merge_sort(arr):

    """

    Main function for merge sort.

    Parameters:

    arr (list): The list to be sorted.

    Returns:

    list: A new sorted list (for clarity, this implementation returns a new list).

    """

    # Base case: if array length is 0 or 1, it's already sorted

    if len(arr)<=1:

        return arr

    # 1. Divide: find the midpoint, 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 hold 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<= right: # Note using <= to maintain sorting stability

            sorted_list.append(left)

            i +=1

        else:

            sorted_list.append(right)

            j +=1

    # 4. Handle remaining elements: append all remaining elements from the left or right list to the result

    # Since left and right are themselves sorted, the remaining elements are definitely larger than all merged elements

    sorted_list.extend(left[i:])

    sorted_list.extend(right[j:])

    return sorted_list

# Run the algorithm using the 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:

Original array: [38, 27, 43, 3, 9, 82, 10]
After merge sort: [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 in the following table:

Metric	Complexity	Description
Time Complexity	O(n log n)	This is the most significant advantage of merge sort. log n comes from the number of recursive levels (splitting the array in half), and n comes from the need to traverse all elements in the merge operation at each level. 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 merge process requires additional space equal to the size of the original array to store the temporary array. This is the main drawback of merge sort.
Stability	Stable	In the merge function, when left == right, we prioritize taking left (using the <= comparison), which ensures that the original relative order of equal elements remains unchanged.
In-place Sorting	No	Requires additional memory space.

---

More Code Examples