Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms in JavaScript

Merge Sort

Explore how merge sort recursively divides an array into smaller halves, sorts them, and merges the results to produce a fully sorted array. This lesson explains the algorithm's step-by-step process, JavaScript implementation, and analyzes its time and space complexity. Understand when to use merge sort, its advantages like stability and consistent performance, and limitations such as extra memory usage.

We'll cover the following...

Imagine you have a large stack of exam papers sorted by student ID, but they got mixed up. Instead of trying to sort the whole stack in one go, you split it into smaller piles, sort those smaller piles, and then carefully merge them back together.

That is the main idea of merge sort. It breaks a big problem into smaller, identical problems, solves them recursively, and combines the results in order.

Merge sort is a divide-and-conquer sorting algorithm that recursively splits an array into smaller halves, sorts each half, and then merges the sorted halves into one final sorted array.

Core idea: Splitting is easy. The real work happens in the merge step, where two already sorted halves are combined into one sorted result.

How it works

Merge sort has two repeating phases. First, it splits the array until each piece is small enough to be trivially sorted. Then it merges those pieces in sorted order.

  • Divide: Split the array into two halves.

  • Conquer: Recursively sort each half.

  • Combine: Merge the two sorted halves into one sorted array.

Base case: An array of length 0 or 1 is already sorted, so the recursion stops there.

Interactive animation

The animation below highlights the recursive split-and-merge structure. It is not just about moving values around. It is about building sorted halves and then combining them.

Algorithm

Before writing JavaScript code, read through the algorithm and connect each step to the trace above.

  1. If the list has one element or is empty:

    1. It is already sorted, so return it.

  2. Otherwise:

    1. Divide the list into two halves:

      1. Left half

      2. Right half

    2. Recursively sort both halves:

      1. Sort the left half

      2. Sort the right half

    3. Merge the two sorted halves:

      1. Create an empty result list.

      2. While both halves have elements:

        1. Compare the first element of each half.

        2. Append the smaller ...