Merge Sort vs Quick Sort, step by step.

Merge sort and quick sort are divide-and-conquer sorts averaging O(n log n). Merge sort splits in the middle and merges: O(n log n) always and stable, but it needs O(n) extra memory. Quick sort partitions around a pivot in place and is usually faster, but can take O(n²). Choose merge sort for stability or guaranteed time, quick sort for speed.

Below, both sort the same array step by step, so you can compare them move by move.

Merge sort vs quick sort: what differs

Merge sort and quick sort on the same array

Both players sort 5, 2, 1, 4, 0, 6, 3, the quick sort topic's default array, from start to finish. Merge sort splits down to single values and compares only in the merges, moving values through an auxiliary array below. Quick sort compares from its first pass and swaps inside the array; each pivot it places turns green and is final. Here merge sort makes 14 comparisons, the most it can need for seven values, and quick sort 12.

Merge sort on 5, 2, 1, 4, 0, 6, 3

All steps as text
  1. Sort the array using the Merge Sort algorithm.
  2. Divide the array into two halves (subarrays). The left half contains indices [0, 3], and the right half contains indices [4, 6].
  3. Focus on the left half [5, 2, 1, 4]. Process the right half [0, 6, 3] later.
  4. Split into [5, 2] and [1, 4].
  5. Examine the left subarray [5, 2]. Process the right subarray [1, 4] afterward.
  6. Both subarrays contain single items, so they are already sorted. Merge them now.
  7. Use the auxiliary array.
  8. Mark the minimum value from the left subarray — currently 5.
  9. Mark the minimum value from the right subarray — currently 2. Compare and merge these into the auxiliary array in sorted order.
  10. Since 2 is smaller than 5, copy 2 first to the auxiliary array.
  11. Copy 5 next.
  12. Transfer values from the auxiliary array back to the original array.
  13. Confirm that the merged part [2, 5] is sorted.
  14. Focus on the right subarray [1, 4] and sort it in the same way.
  15. Both subarrays contain single items, so they are already sorted. Merge them now.
  16. Use the auxiliary array again for the merging process.
  17. Mark the minimum value from the left subarray — currently 1.
  18. Mark the minimum value from the right subarray — currently 4. Compare and merge these into the auxiliary array in sorted order.
  19. Since 1 is smaller than 4, copy 1 first to the auxiliary array.
  20. Copy 4 next.
  21. Transfer values from the auxiliary array back to the original array.
  22. Confirm that the merged part [1, 4] is sorted.
  23. Revisit the subarray [2, 5, 1, 4].
  24. Prepare to merge the sorted subarrays [2, 5] and [1, 4].
  25. Use the auxiliary array again for the merging process.
  26. Mark the minimum value from the left subarray — currently 2.
  27. Mark the minimum value from the right subarray — currently 1. Compare and merge these into the auxiliary array in sorted order.
  28. Since 1 is smaller than 2, copy 1 first to the auxiliary array.
  29. Since 2 is smaller than 4, copy it to the auxiliary array.
  30. Since 4 is smaller than 5, copy it to the auxiliary array.
  31. Copy 5 next.
  32. Transfer values from the auxiliary array back to the original array.
  33. Confirm that the merged part [1, 2, 4, 5] is sorted.
  34. Focus on the right subarray [0, 6, 3] and sort it in the same way.
  35. Split into [0, 6] and [3].
  36. Examine the left subarray [0, 6]. Process the right subarray [3] afterward.
  37. Both subarrays contain single items, so they are already sorted. Merge them now.
  38. Use the auxiliary array again for the merging process.
  39. Mark the minimum value from the left subarray — currently 0.
  40. Mark the minimum value from the right subarray — currently 6. Compare and merge these into the auxiliary array in sorted order.
  41. Since 0 is smaller than 6, copy 0 first to the auxiliary array.
  42. Copy 6 next.
  43. Transfer values from the auxiliary array back to the original array.
  44. Confirm that the merged part [0, 6] is sorted.
  45. Revisit the subarray [0, 6, 3].
  46. Prepare to merge the sorted subarrays [0, 6] and [3].
  47. Use the auxiliary array again for the merging process.
  48. Mark the minimum value from the left subarray — currently 0.
  49. Mark the minimum value from the right subarray — currently 3. Compare and merge these into the auxiliary array in sorted order.
  50. Since 0 is smaller than 3, copy 0 first to the auxiliary array.
  51. Since 3 is smaller than 6, copy it to the auxiliary array.
  52. Copy 6 next.
  53. Transfer values from the auxiliary array back to the original array.
  54. Confirm that the merged part [0, 3, 6] is sorted.
  55. Check the whole array: [1, 2, 4, 5, 0, 3, 6].
  56. Prepare to merge the sorted subarrays [1, 2, 4, 5] and [0, 3, 6].
  57. Use the auxiliary array again for the merging process.
  58. Mark the minimum value from the left subarray — currently 1.
  59. Mark the minimum value from the right subarray — currently 0. Compare and merge these into the auxiliary array in sorted order.
  60. Since 0 is smaller than 1, copy 0 first to the auxiliary array.
  61. Since 1 is smaller than 3, copy it to the auxiliary array.
  62. Since 2 is smaller than 3, copy it to the auxiliary array.
  63. Since 3 is smaller than 4, copy it to the auxiliary array.
  64. Since 4 is smaller than 6, copy it to the auxiliary array.
  65. Since 5 is smaller than 6, copy it to the auxiliary array.
  66. Finally, copy 6.
  67. Transfer values from the auxiliary array back to the original array.
  68. The array is now completely sorted.
  69. Six merges made 14 comparisons, 20 copies into the auxiliary array and 20 back.
Merge Sort vs Quick Sort — Merge sort on 5, 2, 1, 4, 0, 6, 3. Last step: The array is sorted: 0, 1, 2, 3, 4, 5, 6.

Quick sort sorts the same seven values with Lomuto's scheme: the last value of each segment is its pivot.

Quick sort on the same array

All steps as text
  1. Sort the array using the Quick Sort algorithm.
  2. Select the last element as the pivot.
  3. Consider the element at index 0.
  4. Mark this as the leftmost element not less than the pivot. Prepare to swap it with any subsequent element smaller than the pivot, and finally with the pivot itself to complete the partition.
  5. Consider the element at index 1.
  6. Since this element is less than the pivot and a marked element exists, swap them.
  7. Increment the marker by one position after the swap.
  8. Consider the element at index 2.
  9. Since this element is less than the pivot and a marked element exists, swap them.
  10. Increment the marker by one position after the swap.
  11. Consider the element at index 3. Since it is not less than the pivot and the leftmost such element is already marked, take no action.
  12. Consider the element at index 4.
  13. Since this element is less than the pivot and a marked element exists, swap them.
  14. Increment the marker by one position after the swap.
  15. Consider the element at index 5. Since it is not less than the pivot and the leftmost such element is already marked, take no action.
  16. After comparing all elements with the pivot, swap the pivot with the marked element.
  17. Mark the pivot green, as it is now in its final position.
  18. Focus on sorting the subarray obtained from the previous partitioning.
  19. Select the last element as the pivot.
  20. Consider the element at index 0.
  21. Mark this as the leftmost element not less than the pivot. Prepare to swap it with any subsequent element smaller than the pivot, and finally with the pivot itself to complete the partition.
  22. Consider the element at index 1. Since it is not less than the pivot and the leftmost such element is already marked, take no action.
  23. After comparing all elements with the pivot, swap the pivot with the marked element.
  24. Mark the pivot green, as it is now in its final position.
  25. Focus on sorting the subarray obtained from the previous partitioning.
  26. Select the last element as the pivot.
  27. Consider the element at index 1.
  28. Since the element is less than the pivot and no element is marked yet, leave it in place.
  29. Mark the pivot green, as it is now in its final position.
  30. Focus on sorting the subarray obtained from the previous partitioning.
  31. When a segment has only one element, treat it as sorted.
  32. Focus on sorting the subarray obtained from the previous partitioning.
  33. Select the last element as the pivot.
  34. Consider the element at index 4.
  35. Mark this as the leftmost element not less than the pivot. Prepare to swap it with any subsequent element smaller than the pivot, and finally with the pivot itself to complete the partition.
  36. Consider the element at index 5. Since it is not less than the pivot and the leftmost such element is already marked, take no action.
  37. After comparing all elements with the pivot, swap the pivot with the marked element.
  38. Mark the pivot green, as it is now in its final position.
  39. Focus on sorting the subarray obtained from the previous partitioning.
  40. Select the last element as the pivot.
  41. Consider the element at index 5.
  42. Mark this as the leftmost element not less than the pivot. Prepare to swap it with any subsequent element smaller than the pivot, and finally with the pivot itself to complete the partition.
  43. After comparing all elements with the pivot, swap the pivot with the marked element.
  44. Mark the pivot green, as it is now in its final position.
  45. Focus on sorting the subarray obtained from the previous partitioning.
  46. When a segment has only one element, treat it as sorted.
  47. The array is fully sorted.
  48. Five partitions made 12 comparisons with the pivot, three swaps and four pivot swaps, all inside the array itself.
Merge Sort vs Quick Sort — Quick sort on the same array. Last step: The array is sorted: 0, 1, 2, 3, 4, 5, 6.

Merge sort vs quick sort at a glance

Merge sort and quick sort both split an array into parts, sort the parts the same way and stop at parts of one value or none. They split differently, and that one choice decides their worst case, their memory and their stability.

Merge sortQuick sort
SplitsIn the middle, by positionAround a pivot, by value
Main workMerging the sorted halvesPartitioning before the calls
Best and average timeThe same: O(n log n)
Worst timeO(n log n)O(n2)
Extra spaceO(n): the auxiliary arrayO(log n) stack on average, O(n) at worst
In placeNoYes
StableYesNo
Comparisons for seven values: best, average, worst9, 12.7, 1410, 13.5, 21
On the array above14 comparisons, 40 copies12 comparisons, 3 swaps, 4 pivot swaps
Linked listsWell suited: merging relinks nodesPoorly suited
Typical usesStable library sorts, external sortingFast in-memory sorting of arrays

The counts for seven values are over all orders of seven distinct values, quick sort with the app's Lomuto scheme.

Split by position or by value

Both are recursive. In pseudocode, with the names of the topic pages:

mergeSort(a, low, high)
    if low >= high
        return
    mid = floor((low + high) / 2)
    mergeSort(a, low, mid)
    mergeSort(a, mid + 1, high)
    merge(a, low, mid, high)

quickSort(a, low, high)
    if low < high
        p = partition(a, low, high)
        quickSort(a, low, p - 1)
        quickSort(a, p + 1, high)

Merge sort splits at mid without looking at a value, sorts both halves and only then works, in merge. Quick sort works first: partition moves the values smaller than the pivot before it and the rest after it, then the two calls sort the sides. The pivot at p is final and is left out of both calls, and nothing is merged afterward. The merge and partition functions are on the topic pages.

8, 0, 5, 2 splits into two halves: 8, 0 tinted yellow and 5, 2 tinted green.
Merge sort splits by position: 8, 0, 5, 2, the merge sort page's example, becomes 8, 0 and 5, 2, whatever the values.
Arrows from 5, 2, 1, 4, 0, 6, 3 to its partition: 2, 1, 0 under a bracket for values smaller than the pivot, 3 in green, and 5, 6, 4 under a bracket for the rest.
Quick sort splits by value: the first partition of the array above puts 2, 1, 0 before the pivot 3 and 5, 6, 4 after it.

Worst case: why quick sort can take O(n2)

Merge sort always splits in the middle, so its recursion is about log2 n levels deep and each level of merges handles all n values: O(n log n) whatever the input. Quick sort's split depends on the pivot. A pivot near the middle value halves the segment, as merge sort does. A pivot that is the smallest or largest value leaves one side empty, and if that happens every time, there are n levels: O(n2). With the last value as the pivot, input already sorted or reversed is exactly that case, and both are common.

A random pivot gives O(n log n) expected time on any input, and median-of-three, the middle one of the first, middle and last values, cuts the comparisons further. Neither guarantees O(n log n). Introsort does: it is quick sort that switches to heap sort when the recursion gets too deep.

Memory and stability

Merge sort copies each part into an auxiliary array and back, so it needs O(n) extra memory; merging in place is possible, but complex or slower. Quick sort only swaps inside the array. Its extra memory is the recursion stack, O(log n) with even splits; on sorted input the app's code nests one call per value, O(n). Recursing into the smaller side and looping on the larger keeps it O(log n).

Stable means that equal values keep their original order. Merge sort is stable because on a tie it takes the value from the left part, which came first. Quick sort is not: a swap can carry a value over an equal one. In 1, 2a, 2b the pivot is 2b, and its final swap with 2a gives 1, 2b, 2a. Stability matters when records are sorted by one key after another: sorted by name and then by city, each city's records stay in name order.

A row of four cells holding two sorted parts: on the left a 2 marked a and 3, on the right 1 and a 2 marked b. Below it, the auxiliary array holds 1, the 2 marked a, the 2 marked b and 3: the two equal 2s keep their original order.
Merging [2a, 3] and [1, 2b]: on the tie the left 2 goes first, so 2a stays before 2b.
Two rows of three cells, labeled Before and After. Before holds 1, a 2 marked a and a 2 marked b, with the pivot tag under the 2 marked b and the marker flag over the 2 marked a. After holds 1, the 2 marked b in green, and the 2 marked a: the two equal 2s have changed order.
Quick sort's pivot swap carries 2b over 2a: input already in order ends with the equal values reversed.

Which is faster in practice?

On arrays in memory quick sort is usually the faster, though it averages more comparisons for seven values, 13.5 against 12.7. Its inner loop is short, walks the array front to back and swaps within it. Merge sort copies each merged part into the auxiliary array and back: 40 copies for any seven values, while quick sort's run on the array above needs three swaps and four pivot swaps. On small arrays insertion sort runs faster than either, so library sorts hand small parts to it.

What the standard libraries use:

LibrarySortBased on
Python list.sort(), sorted()TimsortMerge sort, stable
Java, arrays of objectsTimSortMerge sort, stable
Java, arrays of int, long, float, doubleDual-pivot quicksortQuick sort
C++ std::sortIntrosort (GCC, LLVM)Quick sort
C++ std::stable_sortMerge sortMerge sort, stable

Only Java chooses by what it sorts: a merge sort for objects, whose equal values must keep their order, and a quick sort for primitive numbers, whose order among equals cannot be seen. Python uses Timsort for everything, and in C++ the caller picks std::sort or std::stable_sort.

When to use merge sort and when to use quick sort

Use merge sort when you need its guarantees:

  • Stability: records sorted by one key after another.
  • A guaranteed worst case: O(n log n) on any input, including input built to slow a sort down.
  • Linked lists: merging relinks nodes, so only the recursion stack is extra.
  • External sorting: data too large for memory is sorted in runs, which are then merged.
  • Parallel sorting: the two halves are independent.

Use quick sort when speed and memory matter more:

  • Large arrays in memory where the order of equal values does not matter.
  • Little spare memory: it sorts in place.
  • Numbers and other plain values, as Java's sorts of primitive arrays do.

Common mix-ups

  • Quick sort is always faster. Usually, not always: with the last value as the pivot, a sorted array is its worst case, 21 comparisons for seven values against merge sort's 11.
  • Quick sort needs no extra memory. It needs its recursion stack: O(log n) on average, O(n) at worst.
  • A sorted array is merge sort's best case. The basic version splits and merges the same way whatever the order. For seven values a sorted array makes 11 comparisons and a reversed one 9, the fewest.
  • Both are adaptive. Neither is in its basic form: input already in order sorts no faster. Timsort is, because it merges runs already in order.
  • Merge sort cannot sort in place. It can, but in-place merging is complex or slower, so the usual version takes O(n) extra memory.

Merge sort vs quick sort interview questions

Both are O(n log n) on average. Why is quick sort usually faster?

It works inside the array, with a short loop that walks it front to back and swaps within it. Merge sort copies each merged part into an auxiliary array and back, which costs time and memory even when the comparisons are fewer.

When would you choose merge sort over quick sort?

When equal values must keep their order, when O(n log n) must hold for every input, when the data is a linked list, and when it is too large for memory and has to be sorted in runs and merged.

What is quick sort's worst case, and how is it avoided?

Every pivot is the smallest or largest value of its segment, so each partition leaves one side empty: n levels and O(n2) time. With the last value as the pivot, sorted input does this. A random pivot or median-of-three makes it unlikely; introsort rules it out by switching to heap sort when the recursion gets too deep.

Why is merge sort stable and quick sort not?

Merge sort takes the left value on a tie, so of two equal values the earlier one stays first. Quick sort swaps values across the array, so one can jump over an equal value: in 1, 2a, 2b the pivot swap puts 2b before 2a.

How deep does the recursion go?

Merge sort's recursion is always about log2 n levels deep, as it halves every part. Quick sort's depends on the pivots: about log2 n with even splits, up to n when every partition leaves one side empty. Recursing into the smaller side first and looping on the larger keeps quick sort's stack O(log n) in every case.

One array here.
Yours in the app.

In VisiGrab, merge sort and quick sort each sort the default, a random or your own array of seven values, step by step, forward and back.

The same array for both

Random picks seven distinct values from 0 to 19, and Custom takes your own from 0 to 99, equal ones included. The last random or custom array comes back in merge sort, quick sort, bubble, selection and insertion sort.

Every step, forward and back

Merge sort shows every split, min label and copy, 75 steps for any seven values; quick sort every pivot, comparison, swap and green mark.

Hoare's partition too

A panel switches quick sort from Lomuto's scheme to Hoare's: two markers scan from both ends, swap and cross, in 59 steps on the default array.

Theory for both

Merge sort's info dialog ends on external sorting. Quick sort's has two tabs: divide and conquer and the three cases, then the partition schemes and pivot selection.

Python, Java and C++

Both sorts in all three languages, quick sort with both partition schemes, linked to the full source on GitHub.

Two quizzes

Eight questions on each sort, with an explanation for every answer.

Split or partition,
on your own array.

Download VisiGrab to step through merge sort and quick sort on the same seven values, yours or random, forward and back.

Merge sort and quick sort each have a topic among 30+. See them all