Sorting

Merge Sort

What is Merge Sort?

Merge Sort takes the divide-and-conquer route: keep splitting the array in half until you're left with pieces of a single element each (which are trivially sorted), then merge those pieces back together two at a time, producing bigger and bigger sorted chunks until only one sorted array remains.

How Does It Work?

Imagine you have an unsorted list of numbers: [38, 27, 43, 3, 9, 82, 10]

  1. Divide the array:
    • [38, 27, 43, 3, 9, 82, 10] splits into [38, 27, 43, 3] and [9, 82, 10]
    • Each half splits again, and again, until every piece holds one element
    • A single element is already sorted — that is the base case where the splitting stops
    382743398210382743398210382743398210382743398210
  2. Merge back up:
    • [38] + [27] → [27, 38], [43] + [3] → [3, 43], [9] + [82] → [9, 82]
    • [27, 38] + [3, 43] → [3, 27, 38, 43], and [9, 82] + [10] → [9, 10, 82]
    • [3, 27, 38, 43] + [9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]
    382743398210273834398210327384391082391027384382
Being dividedSingle element (base case)Merged & sorted

The merge step is where the sorting actually happens. Each half is already sorted, so you only ever compare the two front elements, take the smaller one, and move that pointer forward. Here is the merge of [27, 38] and [3, 43] one comparison at a time:

1. Compare 27 and 3 → 3 is smaller, so it goes out first

leftright27383433merged output

2. Compare 27 and 43 → take 27

leftright2738343327merged output

3. Compare 38 and 43 → take 38

leftright273834332738merged output

4. The left half is empty → copy the rest of the right half

leftright27383433273843merged output
Being comparedTaken into the output

Because each element is looked at once per level and there are log n levels, every merge pass costs O(n) and the whole sort costs O(n log n) — no matter how the input was arranged.

Algorithm Steps

  1. Divide:
    • Find the middle point to divide the array into two halves
    • Recursively call merge sort on the first half
    • Recursively call merge sort on the second half
  2. Merge:
    • Create temporary arrays for both halves
    • Compare elements from each half and merge them in order
    • Copy any remaining elements from either half

Time Complexity

  • Best Case: O(n log n) (already sorted, but still needs all comparisons)
  • Average Case: O(n log n)
  • Worst Case: O(n log n) (consistent performance)

The log n factor comes from the division steps, while the n factor comes from the merge steps.

Space Complexity

Merge Sort requires O(n) additional space for the temporary arrays during merging. This makes it not an in-place sorting algorithm, unlike Insertion Sort or Bubble Sort.

Advantages

  • Stable sorting (maintains relative order of equal elements)
  • Excellent for large datasets (consistent O(n log n) performance)
  • Well-suited for external sorting (sorting data too large for RAM)
  • Easily parallelizable (divide steps can be done concurrently)

Disadvantages

  • Requires O(n) additional space (not in-place)
  • Slower than O(n²) algorithms for very small datasets due to recursion overhead
  • Not as cache-efficient as some other algorithms (e.g., QuickSort)

Merge Sort is particularly useful when sorting linked lists (where random access is expensive) and is the algorithm of choice for many standard library sorting implementations when stability is required. It's also commonly used in external sorting where data doesn't fit in memory.

Daily DSA Challenge by Scale Engineer

Visualize the divide-and-conquer approach of Merge Sort with recursive splitting and merging.

Speed:1x
Comparisons:
0
Merges:
0

Main Array

Generate or enter an array to begin

Test Your Knowledge before moving forward!

Merge Sort Quiz Challenge

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • Earn stars based on your final score (max 5 stars)

Merge Sort Implementation

// Merge Sort in JavaScript
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  
  return merge(left, right);
}

function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;
  
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex++]);
    } else {
      result.push(right[rightIndex++]);
    }
  }
  
  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

// Usage
const arr = [38, 27, 43, 3, 9, 82, 10];
console.log("Original:", arr);
console.log("Sorted:", mergeSort(arr));

Done With the Learning

Mark Merge Sort as done and view it on your dashboard

Explore Sorting Algorithms

Selection Sort

Bubble Sort

Insertion Sort

Quick Sort

Heap Sort