Merge Sort Implementation

Problem Statement

Sort an array using merge sort: split the array into two halves, recursively sort each half, and merge the two sorted halves back together.

Example

Input:  [38, 27, 43, 3, 9, 82, 10]
Split -> sort halves -> merge
Output: [3, 9, 10, 27, 38, 43, 82]

Approach

Merge sort is a classic divide-and-conquer algorithm. The merge step walks two sorted lists with two pointers, always taking the smaller front element, which keeps equal elements in their original order (stability). Its O(n log n) time holds for every input, making it very predictable.

Complexity

• Time: O(n log n) in all cases
• Space: O(n)

Solution Code

Python

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return _merge(left, right)

def _merge(a, b):
    res, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            res.append(a[i]); i += 1
        else:
            res.append(b[j]); j += 1
    res.extend(a[i:])
    res.extend(b[j:])
    return res

Java

int[] mergeSort(int[] arr) {
    if (arr.length <= 1) return arr;
    int mid = arr.length / 2;
    int[] left = mergeSort(Arrays.copyOfRange(arr, 0, mid));
    int[] right = mergeSort(Arrays.copyOfRange(arr, mid, arr.length));
    int[] res = new int[arr.length];
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length)
        res[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
    while (i < left.length) res[k++] = left[i++];
    while (j < right.length) res[k++] = right[j++];
    return res;
}

C++

vector<int> mergeSort(vector<int> arr) {
    if (arr.size() <= 1) return arr;
    int mid = arr.size() / 2;
    vector<int> left(arr.begin(), arr.begin() + mid);
    vector<int> right(arr.begin() + mid, arr.end());
    left = mergeSort(left); right = mergeSort(right);
    vector<int> res;
    int i = 0, j = 0;
    while (i < (int)left.size() && j < (int)right.size())
        res.push_back(left[i] <= right[j] ? left[i++] : right[j++]);
    while (i < (int)left.size()) res.push_back(left[i++]);
    while (j < (int)right.size()) res.push_back(right[j++]);
    return res;
}

Key Takeaways

• Merge sort guarantees O(n log n) and is stable — ideal when worst-case matters.
• It needs O(n) extra space; linked lists can merge with O(1) extra.
• Reference: CLRS, Ch. 2; Wikipedia, "Merge sort".