DSA Tracker

Visualize

Merge Sort

Divide into singles, then merge back sorted

time O(n log n)space O(n)

A single element is trivially 'sorted', so recursively split the array in half until every piece is down to one element — that's the free part. All the real work happens on the way back up: merge two already-sorted halves by repeatedly comparing their fronts and taking the smaller, then appending whatever's left. Because merging two sorted lists is O(n), and there are O(log n) levels of splitting, the whole sort is O(n log n).

Details

Animated on: arr = [38,27,43,3,9,82,10] — sort the array.

Problem:Merge SortMedium

Divide into singles, then merge back sorted

step 1 / 10

38
[0]
27
[1]
43
[2]
3
[3]
9
[4]
82
[5]
10
[6]

Start with the whole array. Recursively split it in half until every subarray holds a single element.

Pseudocode
1FUNCTION mergeSort(arr):
2  IF the length of arr is 1 or less: RETURN arr
3  mid = the length of arr divided by 2
4  left = mergeSort(the first half of arr)
5  right = mergeSort(the second half of arr)
6  RETURN merge(left, right)
7FUNCTION merge(left, right):
8  compare the fronts of left and right, take the smaller, repeat
9  append whatever elements are left over
10  RETURN the merged array

← / → step · space play · Home restart

Every step in words

Show all 10 steps
  1. Start with the whole array. Recursively split it in half until every subarray holds a single element.
  2. Left half: [38,27,43,3] (indices 0-3).
  3. Right half: [9,82,10] (indices 4-6).
  4. Splitting continues until every piece is a single element: [38],[27],[43],[3],[9],[82],[10]. Now merging begins.
  5. Within the left half, [38,27]->[27,38] and [43,3]->[3,43] merge first. Now merge those two pairs: compare 27 vs 3 — 3 is smaller, take 3.
  6. Compare 27 vs 43 — 27 is smaller, take 27.
  7. Compare 38 vs 43 — 38 is smaller, take 38. Only 43 remains — append it.
  8. Left half fully merges into [3,27,38,43].
  9. ...and the right branch fully merges into [9,10,82] ([9] merged with the [10,82] we just built).
  10. Final merge combines [3,27,38,43] and [9,10,82] into the fully sorted array: [3,9,10,27,38,43,82].

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Merge Sort in the editorAll Sorting problemsBack to roadmap