Merge Sort vs. Quick Sort

The following video explains Merge sort, and compares it with Quick sort.

So which algorithm is faster on average?

Let's start with a table that summarizes the results of 2000 random runs:

Merge SortQuick Sort
ComparisonsMin.1719
Max.2543
Avg.22.724.4
Time (seconds)Min.42.636.7
Max.51.675.8
Avg.47.848.4

According to these results, merge sort is a bit faster on average than quick sort. Note however that this data applies to the specific setting of this competition, i.e., ten elements, and various arbitrary details regarding the behavior of the robots.

Here are a few more general notes:

  • Merge sort generally performs less comparisons than quick sort both worst case and on average. If performing a comparison is costly, merge sort will definitely have the upper hand in terms of speed.
  • Merge sort requires more memory: As shown in the video, merge sort uses the whole upper shelf. Quick sort on the other hand puts only one ball at a time on the upper shelf.
  • Quick sort is generally believed to faster in common real-life settings. This is mainly due to its lower memory consumption which usually affects time performance as well.
  • Note that in the video both algorithms do something obviously wasteful. When merge sort merges two balls it can merge them in place, and not move them to the upper shelf and then push them back. This will save it about 2 seconds. Quick sort doesn't really need to push the buttons it pushes when a pivot is placed back (it made sense in the match against bubble sort). This will save it about 3.5 seconds. So after these improvements, quick sort will be a bit faster.

Next: Heap sort

See also

Visualization of Einstein's Relativity
Watch on Youtube >>

Zuto: The Adventures of a Computer Virus
An entertaining book about computer science of ages 9+.

New!
A demonstration of data compression. Visit page >>

An adder built from logic gates
An interactive demonstration of how logic gates work.
Visit page >>