Sorting

Merge Sort

What is Merge Sort?

Merge Sort is an efficient, stable, comparison-based sorting algorithm that follows the divide-and-conquer approach. It works by recursively dividing the unsorted list into sublists until each sublist contains a single element, then repeatedly merges these sublists to produce new sorted sublists until there is only one sorted list remaining.

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.

Time Complexity Analysis

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 Hello World

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