Sorting Head-to-Head Comparison

graph LR
	ALG(["fas:fa-trophy Head-to-Head Comparison fas:fa-trophy #160;"])

	ASY_ANA(["fas:fa-check Asymptotic Analysis #160;"])
  click ASY_ANA "./math-asymptotic-analysis"

	BS(["fas:fa-check Bubble Sort #160;"])
  click BS "./sorting-bubble"

	IS(["fas:fa-check Insertion Sort #160;"])
  click IS "./sorting-insertion"

	SS(["fas:fa-check Selection Sort #160;"])
  click SS "./sorting-selection"

	MS(["fas:fa-check Merge Sort #160;"])
  click MS "./sorting-merge"

	QS(["fas:fa-check Quick Sort #160;"])
  click QS "./sorting-quick"

	ARRAY(["fas:fa-check Array #160;"])
  click ARRAY "./list-data-struct-array"

	ASY_ANA-->ALG
  ARRAY-->BS-->ALG
  ARRAY-->IS-->ALG
  ARRAY-->SS-->ALG
  ARRAY-->MS-->ALG
  ARRAY-->QS-->ALG

Recall from this section’s introduction that sorting algorithms are one of the most heavily researched areas of computer science. Sorting is a ubiquitous need in the software industry and one could devote years of study to the subject. An epiphenomenon of this fact is that all modern languages come equipped with one or more generic sorting primitives. It’s highly unlikely that a software professional will ever need to implement a sort algorithm. This does not suggest that studying sorting is not worthwhile; quite the contrary in fact. Sorting is an ideal space for learning algorithmic analysis and design techniques.

With this section complete, students should have a firm conception of asymptotic analysis as well as a couple techniques for keeping code DRY. Specifically, generic programming and the strategy pattern. Having used these techniques in five different sorting algorithms, they should be ready to transfer the skills to other contexts.

The final learning task is to compare and contrast all the sorting algorithms covered in this section. The table below summarizes their runtime characteristics.

An ongoing theme in this material is that asymptotic complexity, while important, only tells a part of the story. The marriage of theoretical analysis and empirical scrutiny is imperative. That is the purpose of the following subsection.

Actual Run Times

This subsection presents actual runtime² data. The reader is encouraged to experiment by re-producing the data below on their own machine, making modifications, and examining the results. Instructions for generating run time data are available in the Actual Run Times section of the Source Code page.

The charts and accompanying tables below outline the actual run times² incurred by sorting integer arrays of size n using the five algorithms covered in this section.

1. Bubble Sort
2. Insertion Sort
3. Selection Sort
4. Merge Sort
5. Quick Sort

As a reference point, runtime data for C’s built-in qsort³ function are also included. In order to demonstrate the best and worst runtime scenarios, the data is collected using three different types of input data:

1. Randomly Sorted Array
2. Array Sorted in Ascending Order
3. Array Sorted in Descending Order

Randomly Ordered Array

Key Takeaways:

• Quick Sort, Merge Sort, and C’s qsort all perform fairly consistently
• Bubble Sort is the worst performer by a wide margin
• Bubble Sort, Insertion Sort, and Selection Sort perform well when $n \leq 10000$; however, the performance degrades exponentially with higher input sizes

Array Sorted in Ascending Order

Key Takeaways:

• Bubble Sort even outperforms C qsort with pre-sorted input data
• Insertion Sort is $\approx 4560$ times faster than Selection Sort when $n=100000$ and the input data is pre-sorted

Array Sorted in Descending Order

Key Takeaways:

• Bubble Sort is $\approx 10260$ times slower than Quick Sort and Merge Sort when $n = 100000$ and the input data is sorted in reverse order
• Selection Sort is $\approx 2.5$ times faster than Insertion Sort when $n=100000$ and the input data is sorted in reverse order

Source Code

Full Repo

Relevant Files:

• compare_times.py
• algo_timer.c

Click here for details on generating actual run time data

Exercises

1. Using the programming language of your choice, collect runtime data from your own sorting algorithm implementations and compare them to the data supplied here.