So which algorithm is faster on average?
Let’s start with a table that summarizes the results of 2000 random runs:
| Merge Sort | Quick Sort | ||
|---|---|---|---|
| Comparisons | Min. | 17 | 19 |
| Max. | 25 | 43 | |
| Avg. | 22.7 | 24.4 | |
| Time (seconds) | Min. | 42.6 | 36.7 |
| Max. | 51.6 | 75.8 | |
| Avg. | 47.8 | 48.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.