Algorithm Search⌘K

See Merge sort run

Sort an array by divide and conquer. Sort each half, then merge the two sorted halves into one sorted array. Use the buttons or the keys: Space plays and pauses, the arrow keys step, Home and End jump.

  1. MERGE-SORT(A, lo, hi) ▷ sort A[lo .. hi − 1]
  2. 1if hi − lo ≤ 1 then return
  3. 2mid ← lo + ⌊(hi − lo) / 2⌋
  4. 3MERGE-SORT(A, lo, mid)
  5. 4MERGE-SORT(A, mid, hi)
  6. 5MERGE(A, lo, mid, hi)
  7. MERGE(A, lo, mid, hi) ▷ A[lo .. mid − 1] and A[mid .. hi − 1] are sorted
  8. 6B ← a copy of A[lo .. mid − 1]
  9. 7i ← 0, j ← mid, k ← lo
  10. 8while i < |B| and j < hi do
  11. 9if B[i] ≤ A[j] then A[k] ← B[i], i ← i + 1 ▷ ≤ keeps the sort stable
  12. 10else A[k] ← A[j], j ← j + 1
  13. 11k ← k + 1
  14. 12while i < |B| do
  15. 13A[k] ← B[i], i ← i + 1, k ← k + 1
0 / 0
Use your own input

Type the input as JSON, in the same form as a preset.

Open the full player

Read the full page about Merge sort. To put this player on your site, use <iframe src="https://algorithm.tamnd.com/embed/merge-sort/" width="100%" height="520"></iframe>.