Merge Sort

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.

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 ...