Skip to content
Welcome to contribute to Chinese-to-English translation! For more details, please refer to CONTRIBUTING.md.

# 11.6 Merge Sort

Merge sort is a sorting algorithm based on a divide-and-conquer strategy, consisting of the "divide" and "merge" phases shown in Figure 11-10.

1. Divide phase: Recursively split the array at the midpoint, reducing the problem of sorting a long array to the problem of sorting shorter arrays.
2. Merge phase: When a sub-array has length 1, stop dividing and start merging, continuously combining the shorter sorted sub-arrays on the left and right into a longer sorted array until the process is complete.

Figure 11-10 Divide and merge phases of merge sort

## 11.6.1 Algorithm Flow

As shown in Figure 11-11, the "divide phase" recursively splits the array from the midpoint into two sub-arrays from top to bottom.

1. Calculate the array midpoint `mid`, recursively divide the left sub-array (interval `[left, mid]`) and right sub-array (interval `[mid + 1, right]`).
2. Repeat step `1.` recursively until a sub-array has length 1.

The "merge phase" merges the left and right sub-arrays into a sorted array from bottom to top. Note that merging starts from sub-arrays of length 1, so every sub-array involved in this phase is already sorted.

<1><2><3><4><5><6><7><8><9><10>

Figure 11-11 Merge sort steps

The recursive order of merge sort is consistent with the post-order traversal of a binary tree.

- Post-order traversal: First recursively traverse the left subtree, then recursively traverse the right subtree, and finally process the root node.
- Merge sort: First recursively process the left sub-array, then recursively process the right sub-array, and finally perform the merge.

The implementation of merge sort is shown in the code below. Note that the interval to be merged in `nums` is `[left, right]`, while the corresponding interval in `tmp` is `[0, right - left]`.

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
merge_sort.py

    def merge(nums: list[int], left: int, mid: int, right: int):
        """Merge left subarray and right subarray"""
        # Left subarray interval is [left, mid], right subarray interval is [mid+1, right]
        # Create a temporary array tmp to store the merged results
        tmp = [0] * (right - left + 1)
        # Initialize the start indices of the left and right subarrays
        i, j, k = left, mid + 1, 0
        # While both subarrays still have elements, compare and copy the smaller element into the temporary array
        while i <= mid and j <= right:
            if nums[i] <= nums[j]:
                tmp[k] = nums[i]
                i += 1
            else:
                tmp[k] = nums[j]
                j += 1
            k += 1
        # Copy the remaining elements of the left and right subarrays into the temporary array
        while i <= mid:
            tmp[k] = nums[i]
            i += 1
            k += 1
        while j <= right:
            tmp[k] = nums[j]
            j += 1
            k += 1
        # Copy the elements from the temporary array tmp back to the original array nums at the corresponding interval
        for k in range(0, len(tmp)):
            nums[left + k] = tmp[k]

    def merge_sort(nums: list[int], left: int, right: int):
        """Merge sort"""
        # Termination condition
        if left >= right:
            return  # Terminate recursion when subarray length is 1
        # Divide and conquer stage
        mid = (left + right) // 2  # Calculate midpoint
        merge_sort(nums, left, mid)  # Recursively process the left subarray
        merge_sort(nums, mid + 1, right)  # Recursively process the right subarray
        # Merge stage
        merge(nums, left, mid, right)

merge_sort.cpp

    /* Merge left subarray and right subarray */
    void merge(vector<int> &nums, int left, int mid, int right) {
        // Left subarray interval is [left, mid], right subarray interval is [mid+1, right]
        // Create a temporary array tmp to store the merged results
        vector<int> tmp(right - left + 1);
        // Initialize the start indices of the left and right subarrays
        int i = left, j = mid + 1, k = 0;
        // While both subarrays still have elements, compare and copy the smaller element into the temporary array
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j])
                tmp[k++] = nums[i++];
            else
                tmp[k++] = nums[j++];
        }
        // Copy the remaining elements of the left and right subarrays into the temporary array
        while (i <= mid) {
            tmp[k++] = nums[i++];
        }
        while (j <= right) {
            tmp[k++] = nums[j++];
        }
        // Copy the elements from the temporary array tmp back to the original array nums at the corresponding interval
        for (k = 0; k < tmp.size(); k++) {
            nums[left + k] = tmp[k];
        }
    }

    /* Merge sort */
    void mergeSort(vector<int> &nums, int left, int right) {
        // Termination condition
        if (left >= right)
            return; // Terminate recursion when subarray length is 1
        // Divide and conquer stage
        int mid = left + (right - left) / 2;    // Calculate midpoint
        mergeSort(nums, left, mid);      // Recursively process the left subarray
        mergeSort(nums, mid + 1, right); // Recursively process the right subarray
        // Merge stage
        merge(nums, left, mid, right);
    }

merge_sort.java

    /* Merge left subarray and right subarray */
    void merge(int[] nums, int left, int mid, int right) {
        // Left subarray interval is [left, mid], right subarray interval is [mid+1, right]
        // Create a temporary array tmp to store the merged results
        int[] tmp = new int[right - left + 1];
        // Initialize the start indices of the left and right subarrays
        int i = left, j = mid + 1, k = 0;
        // While both subarrays still have elements, compare and copy the smaller element into the temporary array
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j])
                tmp[k++] = nums[i++];
            else
                tmp[k++] = nums[j++];
        }
        // Copy the remaining elements of the left and right subarrays into the temporary array
        while (i <= mid) {
            tmp[k++] = nums[i++];
        }
        while (j <= right) {
            tmp[k++] = nums[j++];
        }
        // Copy the elements from the temporary array tmp back to the original array nums at the corresponding interval
        for (k = 0; k < tmp.length; k++) {
            nums[left + k] = tmp[k];
        }
    }

    /* Merge sort */
    void mergeSort(int[] nums, int left, int right) {
        // Termination condition
        if (left >= right)
            return; // Terminate recursion when subarray length is 1
        // Divide and conquer stage
        int mid = left + (right - left) / 2; // Calculate midpoint
        mergeSort(nums, left, mid); // Recursively process the left subarray
        mergeSort(nums, mid + 1, right); // Recursively process the right subarray
        // Merge stage
        merge(nums, left, mid, right);
    }

merge_sort.cs

    /* Merge left subarray and right subarray */
    void Merge(int[] nums, int left, int mid, int right) {
        // Left subarray interval is [left, mid], right subarray interval is [mid+1, right]
        // Create a temporary array tmp to store the merged results
        int[] tmp = new int[right - left + 1];
        // Initialize the start indices of the left and right subarrays
        int i = left, j = mid + 1, k = 0;
        // While both subarrays still have elements, compare and copy the smaller element into the temporary array
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j])
                tmp[k++] = nums[i++];
            else
                tmp[k++] = nums[j++];
        }
        // Copy the remaining elements of the left and right subarrays into the temporary array
        while (i <= mid) {
            tmp[k++] = nums[i++];
        }
        while (j <= right) {
            tmp[k++] = nums[j++];
        }
        // Copy the elements from the temporary array tmp back to the original array nums at the corresponding interval
        for (k = 0; k < tmp.Length; ++k) {
            nums[left + k] = tmp[k];
        }
    }

    /* Merge sort */
    void MergeSort(int[] nums, int left, int right) {
        // Termination condition
        if (left >= right) return;       // Terminate recursion when subarray length is 1
        // Divide and conquer stage
        int mid = left + (right - left) / 2;    // Calculate midpoint
        MergeSort(nums, left, mid);      // Recursively process the left subarray
        MergeSort(nums, mid + 1, right); // Recursively process the right subarray
        // Merge stage
        Merge(nums, left, mid, right);
    }

merge_sort.go

    /* Merge left subarray and right subarray */
    func merge(nums []int, left, mid, right int) {
        // Left subarray interval is [left, mid], right subarray interval is [mid+1, right]
        // Create a temporary array tmp to store the merged results
        tmp := make([]int, right-left+1)
        // Initialize the start indices of the left and right subarrays
        i, j, k := left, mid+1, 0
        // While both subarrays still have elements, compare and copy the smaller element into the temporary array
        for i <= mid && j <= right {
            if nums[i] <= nums[j] {
                tmp[k] = nums[i]
                i++
            } else {
                tmp[k] = nums[j]
                j++
            }
            k++
        }
        // Copy the remaining elements of the left and right subarrays into the temporary array
        for i <= mid {
            tmp[k] = nums[i]
            i++
            k++
        }
        for j <= right {
            tmp[k] = nums[j]
            j++
            k++
        }
        // Copy the elements from the temporary array tmp back to the original array nums at the corresponding interval
        for k := 0; k < len(tmp); k++ {
            nums[left+k] = tmp[k]
        }
    }

    /* Merge sort */
    func mergeSort(nums []int, left, right int) {
        // Termination condition
        if left >= right {
            return
        }
        // Divide and conquer stage
        mid := left + (right - left) / 2
        mergeSort(nums, left, mid)
        mergeSort(nums, mid+1, right)
        // Merge stage
        merge(nums, left, mid, right)
    }

merge_sort.swift

    /* Merge left subarray and right subarray */
    func merge(nums: inout [Int], left: Int, mid: Int, right: Int) {
        // Left subarray interval is [left, mid], right subarray interval is [mid+1, right]
        // Create a temporary array tmp to store the merged results
        var tmp = Array(repeating: 0, count: right - left + 1)
        // Initialize the start indices of the left and right subarrays
        var i = left, j = mid + 1, k = 0
        // While both subarrays still have elements, compare and copy the smaller element into the temporary array
        while i <= mid, j <= right {
            if nums[i] <= nums[j] {
                tmp[k] = nums[i]
                i += 1
            } else {
                tmp[k] = nums[j]
                j += 1
            }
            k += 1
        }
        // Copy the remaining elements of the left and right subarrays into the temporary array
        while i <= mid {
            tmp[k] = nums[i]
            i += 1
            k += 1
        }
        while j <= right {
            tmp[k] = nums[j]
            j += 1
            k += 1
        }
        // Copy the elements from the temporary array tmp back to the original array nums at the corresponding interval
        for k in tmp.indices {
            nums[left + k] = tmp[k]
        }
    }

    /* Merge sort */
    func mergeSort(nums: inout [Int], left: Int, right: Int) {
        // Termination condition
        if left >= right { // Terminate recursion when subarray length is 1
            return
        }
        // Divide and conquer stage
        let mid = left + (right - left) / 2 // Calculate midpoint
        mergeSort(nums: &nums, left: left, right: mid) // Recursively process the left subarray
        mergeSort(nums: &nums, left: mid + 1, right: right) // Recursively process the right subarray
        // Merge stage
        merge(nums: &nums, left: left, mid: mid, right: right)
    }

merge_sort.js

    /* Merge left subarray and right subarray */
    function merge(nums, left, mid, right) {
        // Left subarray interval is [left, mid], right subarray interval is [mid+1, right]
        // Create a temporary array tmp to store the merged results
        const tmp = new Array(right - left + 1);
        // Initialize the start indices of the left and right subarrays
        let i = left,
            j = mid + 1,
            k = 0;
        // While both subarrays still have elements, compare and copy the smaller element into the temporary array
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                tmp[k++] = nums[i++];
            } else {
                tmp[k++] = nums[j++];
            }
        }
        // Copy the remaining elements of the left and right subarrays into the temporary array
        while (i <= mid) {
            tmp[k++] = nums[i++];
        }
        while (j <= right) {
            tmp[k++] = nums[j++];
        }
        // Copy the elements from the temporary array tmp back to the original array nums at the corresponding interval
        for (k = 0; k < tmp.length; k++) {
            nums[left + k] = tmp[k];
        }
    }

    /* Merge sort */
    function mergeSort(nums, left, right) {
        // Termination condition
        if (left >= right) return; // Terminate recursion when subarray length is 1
        // Divide and conquer stage
        let mid = Math.floor(left + (right - left) / 2); // Calculate midpoint
        mergeSort(nums, left, mid); // Recursively process the left subarray
        mergeSort(nums, mid + 1, right); // Recursively process the right subarray
        // Merge stage
        merge(nums, left, mid, right);
    }

merge_sort.ts

    /* Merge left subarray and right subarray */
    function merge(nums: number[], left: number, mid: number, right: number): void {
        // Left subarray interval is [left, mid], right subarray interval is [mid+1, right]
        // Create a temporary array tmp to store the merged results
        const tmp = new Array(right - left + 1);
        // Initialize the start indices of the left and right subarrays
        let i = left,
            j = mid + 1,
            k = 0;
        // While both subarrays still have elements, compare and copy the smaller element into the temporary array
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                tmp[k++] = nums[i++];
            } else {
                tmp[k++] = nums[j++];
            }
        }
        // Copy the remaining elements of the left and right subarrays into the temporary array
        while (i <= mid) {
            tmp[k++] = nums[i++];
        }
        while (j <= right) {
            tmp[k++] = nums[j++];
        }
        // Copy the elements from the temporary array tmp back to the original array nums at the corresponding interval
        for (k = 0; k < tmp.length; k++) {
            nums[left + k] = tmp[k];
        }
    }

    /* Merge sort */
    function mergeSort(nums: number[], left: number, right: number): void {
        // Termination condition
        if (left >= right) return; // Terminate recursion when subarray length is 1
        // Divide and conquer stage
        let mid = Math.floor(left + (right - left) / 2); // Calculate midpoint
        mergeSort(nums, left, mid); // Recursively process the left subarray
        mergeSort(nums, mid + 1, right); // Recursively process the right subarray
        // Merge stage
        merge(nums, left, mid, right);
    }

merge_sort.dart

    /* Merge left subarray and right subarray */
    void merge(List<int> nums, int left, int mid, int right) {
      // Left subarray interval is [left, mid], right subarray interval is [mid+1, right]
      // Create a temporary array tmp to store the merged results
      List<int> tmp = List.filled(right - left + 1, 0);
      // Initialize the start indices of the left and right subarrays
      int i = left, j = mid + 1, k = 0;
      // While both subarrays still have elements, compare and copy the smaller element into the temporary array
      while (i <= mid && j <= right) {
        if (nums[i] <= nums[j])
          tmp[k++] = nums[i++];
        else
          tmp[k++] = nums[j++];
      }
      // Copy the remaining elements of the left and right subarrays into the temporary array
      while (i <= mid) {
        tmp[k++] = nums[i++];
      }
      while (j <= right) {
        tmp[k++] = nums[j++];
      }
      // Copy the elements from the temporary array tmp back to the original array nums at the corresponding interval
      for (k = 0; k < tmp.length; k++) {
        nums[left + k] = tmp[k];
      }
    }

    /* Merge sort */
    void mergeSort(List<int> nums, int left, int right) {
      // Termination condition
      if (left >= right) return; // Terminate recursion when subarray length is 1
      // Divide and conquer stage
      int mid = left + (right - left) ~/ 2; // Calculate midpoint
      mergeSort(nums, left, mid); // Recursively process the left subarray
      mergeSort(nums, mid + 1, right); // Recursively process the right subarray
      // Merge stage
      merge(nums, left, mid, right);
    }

merge_sort.rs

    /* Merge left subarray and right subarray */
    fn merge(nums: &mut [i32], left: usize, mid: usize, right: usize) {
        // Left subarray interval is [left, mid], right subarray interval is [mid+1, right]
        // Create a temporary array tmp to store the merged results
        let tmp_size = right - left + 1;
        let mut tmp = vec![0; tmp_size];
        // Initialize the start indices of the left and right subarrays
        let (mut i, mut j, mut k) = (left, mid + 1, 0);
        // While both subarrays still have elements, compare and copy the smaller element into the temporary array
        while i <= mid && j <= right {
            if nums[i] <= nums[j] {
                tmp[k] = nums[i];
                i += 1;
            } else {
                tmp[k] = nums[j];
                j += 1;
            }
            k += 1;
        }
        // Copy the remaining elements of the left and right subarrays into the temporary array
        while i <= mid {
            tmp[k] = nums[i];
            k += 1;
            i += 1;
        }
        while j <= right {
            tmp[k] = nums[j];
            k += 1;
            j += 1;
        }
        // Copy the elements from the temporary array tmp back to the original array nums at the corresponding interval
        for k in 0..tmp_size {
            nums[left + k] = tmp[k];
        }
    }

    /* Merge sort */
    fn merge_sort(nums: &mut [i32], left: usize, right: usize) {
        // Termination condition
        if left >= right {
            return; // Terminate recursion when subarray length is 1
        }

        // Divide and conquer stage
        let mid = left + (right - left) / 2; // Calculate midpoint
        merge_sort(nums, left, mid); // Recursively process the left subarray
        merge_sort(nums, mid + 1, right); // Recursively process the right subarray

        // Merge stage
        merge(nums, left, mid, right);
    }

merge_sort.c

    /* Merge left subarray and right subarray */
    void merge(int *nums, int left, int mid, int right) {
        // Left subarray interval is [left, mid], right subarray interval is [mid+1, right]
        // Create a temporary array tmp to store the merged results
        int tmpSize = right - left + 1;
        int *tmp = (int *)malloc(tmpSize * sizeof(int));
        // Initialize the start indices of the left and right subarrays
        int i = left, j = mid + 1, k = 0;
        // While both subarrays still have elements, compare and copy the smaller element into the temporary array
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                tmp[k++] = nums[i++];
            } else {
                tmp[k++] = nums[j++];
            }
        }
        // Copy the remaining elements of the left and right subarrays into the temporary array
        while (i <= mid) {
            tmp[k++] = nums[i++];
        }
        while (j <= right) {
            tmp[k++] = nums[j++];
        }
        // Copy the elements from the temporary array tmp back to the original array nums at the corresponding interval
        for (k = 0; k < tmpSize; ++k) {
            nums[left + k] = tmp[k];
        }
        // Free memory
        free(tmp);
    }

    /* Merge sort */
    void mergeSort(int *nums, int left, int right) {
        // Termination condition
        if (left >= right)
            return; // Terminate recursion when subarray length is 1
        // Divide and conquer stage
        int mid = left + (right - left) / 2;    // Calculate midpoint
        mergeSort(nums, left, mid);      // Recursively process the left subarray
        mergeSort(nums, mid + 1, right); // Recursively process the right subarray
        // Merge stage
        merge(nums, left, mid, right);
    }

merge_sort.kt

    /* Merge left subarray and right subarray */
    fun merge(nums: IntArray, left: Int, mid: Int, right: Int) {
        // Left subarray interval is [left, mid], right subarray interval is [mid+1, right]
        // Create a temporary array tmp to store the merged results
        val tmp = IntArray(right - left + 1)
        // Initialize the start indices of the left and right subarrays
        var i = left
        var j = mid + 1
        var k = 0
        // While both subarrays still have elements, compare and copy the smaller element into the temporary array
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j])
                tmp[k++] = nums[i++]
            else
                tmp[k++] = nums[j++]
        }
        // Copy the remaining elements of the left and right subarrays into the temporary array
        while (i <= mid) {
            tmp[k++] = nums[i++]
        }
        while (j <= right) {
            tmp[k++] = nums[j++]
        }
        // Copy the elements from the temporary array tmp back to the original array nums at the corresponding interval
        for (l in tmp.indices) {
            nums[left + l] = tmp[l]
        }
    }

    /* Merge sort */
    fun mergeSort(nums: IntArray, left: Int, right: Int) {
        // Termination condition
        if (left >= right) return  // Terminate recursion when subarray length is 1
        // Divide and conquer stage
        val mid = left + (right - left) / 2 // Calculate midpoint
        mergeSort(nums, left, mid) // Recursively process the left subarray
        mergeSort(nums, mid + 1, right) // Recursively process the right subarray
        // Merge stage
        merge(nums, left, mid, right)
    }

merge_sort.rb

    ### Merge left and right subarrays ###
    def merge(nums, left, mid, right)
      # Left subarray interval is [left, mid], right subarray interval is [mid+1, right]
      # Create temporary array tmp to store merged result
      tmp = Array.new(right - left + 1, 0)
      # Initialize the start indices of the left and right subarrays
      i, j, k = left, mid + 1, 0
      # While both subarrays still have elements, compare and copy the smaller element into the temporary array
      while i <= mid && j <= right
        if nums[i] <= nums[j]
          tmp[k] = nums[i]
          i += 1
        else
          tmp[k] = nums[j]
          j += 1
        end
        k += 1
      end
      # Copy the remaining elements of the left and right subarrays into the temporary array
      while i <= mid
        tmp[k] = nums[i]
        i += 1
        k += 1
      end
      while j <= right
        tmp[k] = nums[j]
        j += 1
        k += 1
      end
      # Copy the elements from the temporary array tmp back to the original array nums at the corresponding interval
      (0...tmp.length).each do |k|
        nums[left + k] = tmp[k]
      end
    end

    ### Merge sort ###
    def merge_sort(nums, left, right)
      # Termination condition
      # Terminate recursion when subarray length is 1
      return if left >= right
      # Divide and conquer stage
      mid = left + (right - left) / 2 # Calculate midpoint
      merge_sort(nums, left, mid) # Recursively process the left subarray
      merge_sort(nums, mid + 1, right) # Recursively process the right subarray
      # Merge stage
      merge(nums, left, mid, right)
    end

## 11.6.2 Algorithm Characteristics

- Time complexity is \(O(n \log n)\); merge sort is non-adaptive: The divide phase produces a recursion tree of height \(\log n\), and the total number of operations performed during merging at each level is \(n\), so the overall time complexity is \(O(n \log n)\).
- Space complexity is \(O(n)\); merge sort is not in-place: The recursion depth is \(\log n\), which uses \(O(\log n)\) stack-frame space. The merge operation requires an auxiliary array, which uses \(O(n)\) additional space.
- Stable sort: During merging, the relative order of equal elements remains unchanged.

## 11.6.3 Linked List Sorting

For linked lists, merge sort has significant advantages over other sorting algorithms, and it can reduce the space complexity of the sorting task to \(O(1)\).

- Divide phase: Iteration can be used instead of recursion to split the linked list, thereby eliminating the stack-frame space used by recursion.
- Merge phase: In linked lists, node insertion and deletion require only pointer updates, so the merge phase (merging two short sorted linked lists into one longer sorted linked list) does not require creating an additional linked list.

The specific implementation details are quite complex, and interested readers can consult related materials for learning.

##### Feel free to drop your insights, questions or suggestions