Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Merge Sort

MEDIUMProblemSolveExternal Links

Description

Given an array of integers, sort the array in ascending order using the Merge Sort algorithm.

Merge Sort is a classic divide and conquer sorting algorithm. The idea is deceptively simple:

  1. Divide the array into two halves
  2. Conquer by recursively sorting each half
  3. Merge the two sorted halves back into a single sorted array

The key insight is that merging two already-sorted arrays into one sorted array is a very efficient linear-time operation. By recursively breaking the problem down to arrays of size 1 (which are trivially sorted), then merging upward, we achieve an efficient O(n log n) sort.

You are given the array arr[], its starting position l, and its ending position r. Implement the merge sort algorithm to sort the array.

Examples

Example 1

Input: arr = [4, 1, 3, 9, 7]

Output: [1, 3, 4, 7, 9]

Explanation: The array is sorted in ascending order. Merge sort divides [4,1,3,9,7] into [4,1,3] and [9,7], recursively sorts each half, and merges the sorted halves to produce [1,3,4,7,9].

Example 2

Input: arr = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Explanation: Even when the array is in completely reverse order (the worst case for many sorting algorithms), merge sort efficiently sorts it in O(n log n) time by recursively dividing and merging.

Example 3

Input: arr = [5, 5, 5, 5]

Output: [5, 5, 5, 5]

Explanation: When all elements are identical, the array is already sorted. Merge sort is a stable sorting algorithm — equal elements maintain their relative order.

Constraints

  • 1 ≤ arr.size() ≤ 10^5
  • 1 ≤ arr[i] ≤ 10^5

Editorial

Brute Force

Intuition

Before understanding merge sort, let's first consider the simplest sorting approaches that a beginner might think of.

The most basic idea is selection sort: repeatedly find the minimum element from the unsorted portion and place it at the beginning. You scan the entire remaining array to find the smallest element, swap it to the front, then repeat for the rest.

Imagine you have a shelf of books in random order and you want to sort them by height. The most natural approach: scan all the books to find the shortest one, pull it out and place it first. Then scan the remaining books for the next shortest, and so on. Each scan takes O(n) time, and you do n scans, giving O(n²) total.

This works, but it's slow for large arrays because of the nested scanning.

Step-by-Step Explanation

Let's trace selection sort on arr = [4, 1, 3, 9, 7]:

Step 1: Find the minimum in arr[0..4]. Scan: 4, 1, 3, 9, 7. Minimum is 1 at index 1. Swap arr[0] and arr[1]. Array: [1, 4, 3, 9, 7].

Step 2: Find the minimum in arr[1..4]. Scan: 4, 3, 9, 7. Minimum is 3 at index 2. Swap arr[1] and arr[2]. Array: [1, 3, 4, 9, 7].

Step 3: Find the minimum in arr[2..4]. Scan: 4, 9, 7. Minimum is 4 at index 2. Already in place. Array: [1, 3, 4, 9, 7].

Step 4: Find the minimum in arr[3..4]. Scan: 9, 7. Minimum is 7 at index 4. Swap arr[3] and arr[4]. Array: [1, 3, 4, 7, 9].

Step 5: Only one element left at arr[4]. Already in place.

Result: [1, 3, 4, 7, 9]. Sorted! But we did 4 + 3 + 2 + 1 = 10 comparisons for just 5 elements.

Selection Sort — Find Minimum and Swap — Watch how selection sort repeatedly finds the minimum element from the unsorted portion and swaps it into position, requiring O(n) comparisons per pass.

Algorithm

  1. For each position i from 0 to n-2:
    • Find the index min_idx of the minimum element in arr[i..n-1]
    • Swap arr[i] with arr[min_idx]
  2. After n-1 passes, the array is sorted

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    void selectionSort(vector<int>& arr) {
        int n = arr.size();
        for (int i = 0; i < n - 1; i++) {
            int min_idx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[min_idx]) {
                    min_idx = j;
                }
            }
            swap(arr[i], arr[min_idx]);
        }
    }
};
class Solution:
    def selectionSort(self, arr):
        n = len(arr)
        for i in range(n - 1):
            min_idx = i
            for j in range(i + 1, n):
                if arr[j] < arr[min_idx]:
                    min_idx = j
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
class Solution {
    void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
        }
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop runs n-1 times. For each iteration, the inner loop scans the remaining unsorted elements. Total comparisons: (n-1) + (n-2) + ... + 1 = n(n-1)/2, which is O(n²).

Space Complexity: O(1)

Selection sort is in-place — it only uses a few extra variables (min_idx, temp) regardless of input size.

Why This Approach Is Not Efficient

Selection sort (and other O(n²) algorithms like bubble sort and insertion sort) are too slow for large inputs. With n up to 10^5, an O(n²) algorithm performs approximately 10^10 operations — far beyond what can execute within typical time limits (usually 10^8 operations per second).

The fundamental issue is that these algorithms make too many redundant comparisons. Each element is compared against nearly every other element. There's no way to leverage partial sorting information to skip unnecessary work.

The key insight for improvement: divide and conquer. Instead of sorting the entire array at once, what if we split it into two halves, sort each half independently, and then combine them? Sorting two halves of size n/2 is significantly cheaper than sorting the full array of size n, provided the combining step is efficient.

This is exactly the idea behind Merge Sort: split the array recursively until we reach trivially sorted subarrays (size 1), then merge sorted subarrays back together in O(n) time per level. With log(n) levels of splitting and O(n) work per level, we achieve O(n log n) total — a massive improvement over O(n²).

Optimal Approach - Merge Sort (Divide and Conquer)

Intuition

Merge sort is built on a powerful insight: merging two sorted arrays into one sorted array is easy and fast.

Imagine you have two piles of playing cards, each already sorted from smallest to largest. To merge them into one sorted pile:

  1. Compare the top cards of both piles
  2. Take the smaller card and place it in the output pile
  3. Repeat until one pile is empty
  4. Dump the remaining pile onto the output

This merge operation takes O(n) time because each card is looked at exactly once. The genius of merge sort is using this efficient merge as a building block.

The recursive strategy:

  • Base case: An array of size 0 or 1 is already sorted — do nothing
  • Recursive step: Split the array into left and right halves, recursively sort each half, then merge the two sorted halves

The recursion creates a tree of divisions. At the bottom, we have individual elements (trivially sorted). Then we merge upward: pairs of single elements become sorted pairs, pairs of sorted pairs become sorted quadruples, and so on until the entire array is sorted.

With log₂(n) levels of recursion and O(n) merge work at each level, the total time is O(n log n) — regardless of the initial order of elements.

Merge sort divide-and-conquer tree showing array [4,1,3,9,7] splitting and merging
Merge sort divide-and-conquer tree showing array [4,1,3,9,7] splitting and merging

Step-by-Step Explanation

Let's trace merge sort on arr = [4, 1, 3, 9, 7], focusing on the merge operations:

Division Phase:

  • [4, 1, 3, 9, 7] → split at mid=2 → left=[4, 1, 3], right=[9, 7]
  • [4, 1, 3] → split at mid=1 → left=[4, 1], right=[3]
  • [4, 1] → split at mid=0 → left=[4], right=[1]
  • [4] and [1] are base cases (size 1) — already sorted
  • [9, 7] → split at mid=0 → left=[9], right=[7]
  • [9] and [7] are base cases

Merge Phase (bottom-up):

Step 1: Merge [4] and [1]:

  • Compare 4 vs 1. 1 < 4, take 1. Remaining: [4] and []. Take 4.
  • Result: [1, 4]

Step 2: Merge [1, 4] and [3]:

  • Compare 1 vs 3. 1 < 3, take 1. Compare 4 vs 3. 3 < 4, take 3. Take remaining 4.
  • Result: [1, 3, 4]

Step 3: Merge [9] and [7]:

  • Compare 9 vs 7. 7 < 9, take 7. Take remaining 9.
  • Result: [7, 9]

Step 4: Merge [1, 3, 4] and [7, 9]:

  • Compare 1 vs 7. 1 < 7, take 1.
  • Compare 3 vs 7. 3 < 7, take 3.
  • Compare 4 vs 7. 4 < 7, take 4.
  • Left exhausted. Take remaining [7, 9].
  • Result: [1, 3, 4, 7, 9]

Final Result: [1, 3, 4, 7, 9]

Merge Sort — Merging Sorted Halves Step by Step — Watch the core merge operation in detail. Two sorted subarrays are combined into one sorted result by comparing front elements and taking the smaller one each time.

Algorithm

mergeSort(arr, left, right):

  1. If left >= right, return (base case: 0 or 1 element)
  2. Calculate mid = left + (right - left) / 2
  3. Recursively call mergeSort(arr, left, mid) — sort the left half
  4. Recursively call mergeSort(arr, mid + 1, right) — sort the right half
  5. Call merge(arr, left, mid, right) — merge the two sorted halves

merge(arr, left, mid, right):

  1. Create temporary arrays L[] = arr[left..mid] and R[] = arr[mid+1..right]
  2. Initialize three pointers: i = 0 (for L), j = 0 (for R), k = left (for arr)
  3. While both i < len(L) and j < len(R):
    • If L[i] <= R[j]: place L[i] at arr[k], increment i
    • Else: place R[j] at arr[k], increment j
    • Increment k
  4. Copy remaining elements of L[] (if any) into arr
  5. Copy remaining elements of R[] (if any) into arr

Code

#include <vector>
using namespace std;

class Solution {
public:
    void merge(vector<int>& arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        
        // Create temporary arrays
        vector<int> L(n1), R(n2);
        
        // Copy data into temp arrays
        for (int i = 0; i < n1; i++)
            L[i] = arr[left + i];
        for (int j = 0; j < n2; j++)
            R[j] = arr[mid + 1 + j];
        
        // Merge the two sorted halves back
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
        
        // Copy remaining elements of L[]
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
        
        // Copy remaining elements of R[]
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
    
    void mergeSort(vector<int>& arr, int left, int right) {
        if (left >= right) return;
        
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
};
class Solution:
    def merge(self, arr, left, mid, right):
        # Create temporary arrays
        L = arr[left:mid + 1]
        R = arr[mid + 1:right + 1]
        
        i = j = 0
        k = left
        
        # Merge the two sorted halves
        while i < len(L) and j < len(R):
            if L[i] <= R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1
        
        # Copy remaining elements
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1
        
        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1
    
    def mergeSort(self, arr, left, right):
        if left >= right:
            return
        
        mid = (left + right) // 2
        self.mergeSort(arr, left, mid)
        self.mergeSort(arr, mid + 1, right)
        self.merge(arr, left, mid, right)
class Solution {
    void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        
        // Create temporary arrays
        int[] L = new int[n1];
        int[] R = new int[n2];
        
        // Copy data into temp arrays
        for (int i = 0; i < n1; i++)
            L[i] = arr[left + i];
        for (int j = 0; j < n2; j++)
            R[j] = arr[mid + 1 + j];
        
        // Merge the two sorted halves
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
        
        // Copy remaining elements of L[]
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
        
        // Copy remaining elements of R[]
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
    
    void mergeSort(int[] arr, int left, int right) {
        if (left >= right) return;
        
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

Complexity Analysis

Time Complexity: O(n log n)

The array is recursively divided in half, creating log₂(n) levels of recursion. At each level, the total merge work across all subarrays is O(n) because every element is compared and placed exactly once. Therefore, total time = O(n) × O(log n) = O(n log n).

This holds for all cases — best, average, and worst. Unlike quicksort, merge sort's performance doesn't degrade based on input order.

Recurrence relation: T(n) = 2T(n/2) + O(n), which solves to T(n) = O(n log n) by the Master Theorem.

Space Complexity: O(n)

The merge step requires temporary arrays to hold the left and right halves. At any point, the total extra space used is proportional to the current merge level's subarray size. The maximum extra space is O(n) when merging the final two halves.

Additionally, the recursion stack uses O(log n) space due to log₂(n) levels of recursive calls. The dominant term is O(n) from the temporary merge arrays.

Visualization

Merge Sort — Full Divide and Conquer Visualization