1. Sort function
Define the recursive function that keeps splitting and merging the array.
function mergeSort(arr)Typorithm · medium
Merge Sort
▷ Interactive algorithm labsortingmerge-sortdivide-and-conquerrecursionmerge
Saved on this device
Full lesson · 37 learning steps Open any exercise for focused practice
10%
Step 1 of 37 · intro card
Learn Merge Sort
Sorting Algorithms
Merge Sort divides the array, solves smaller halves, then merges them back in order.
Merge Sort uses divide and conquer. It keeps splitting the array until each piece has one value.
The base case is `arr.length <= 1`: a one-item array is already sorted.
After splitting with `Math.floor(arr.length / 2)`, the left and right halves are recursively sorted.
The merge helper combines sorted halves by repeatedly taking the smaller front value.
Using `left[i] <= right[j]` keeps equal left-side values first, so this implementation is stable.
Preparing algorithm lab…
01
Divide until subarrays have one element.
02
Recursively sort left and right halves.
03
Merge by comparing front values.
04
Time is O(n log n) in best, average, and worst cases.
05
Space is O(n), and this implementation is not in-place.
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) {
const result = [];
let i = 0;
let j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
}
}
return result.concat(left.slice(i), right.slice(j));
}Read the implementation
Connect each part of the code to the concept before you type.
2. Base case
A length 0 or 1 array is already sorted, so recursion stops here.
if (arr.length <= 1) return arr3. Midpoint
Find the integer split point for dividing the array into two halves.
const mid = Math.floor(arr.length / 2)4. Sort left half
Recursively sort the left half before merging it back.
const left = mergeSort(arr.slice(0, mid))5. Sort right half
Recursively sort the right half before merging it back.
const right = mergeSort(arr.slice(mid))6. Merge sorted halves
Combine the two sorted halves into one sorted array.
return merge(left, right)7. Merge helper
This helper repeatedly picks the smaller front value from two sorted arrays.
function merge(left, right)8. Result array
Store the merged output in a new array, which is why this version uses extra space.
const result = []9. Left pointer
Track the current front value in the left sorted half.
let i = 010. Right pointer
Track the current front value in the right sorted half.
let j = 011. Merge loop
Compare front values while both halves still have values available.
while (i < left.length && j < right.length)12. Stable comparison
Use <= so equal values from the left half keep their relative order.
if (left[i] <= right[j])13. Take from left
When the left front value is smaller or equal, add it to the result.
result.push(left[i])14. Advance left
Move to the next value in the left half after taking left[i].
i++15. Take from right
When the right front value is smaller, add it to the result.
result.push(right[j])16. Advance right
Move to the next value in the right half after taking right[j].
j++17. Append leftovers
Append whatever remains after one half runs out.
return result.concat(left.slice(i), right.slice(j))A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.