Heap Sort vs Merge Sort vs Insertion Sort vs Radix Sort vs Counting Sort vs Quick Sort

Mar 19, 2014 · Comments
code sorting algo c++

I had written about sorting algorithms (Tag: Sorting) with details about what to look out for along with their code snippets but I wanted a do a quick comparison of all the algos together to see how do they perform when the same set of input is provided to them. Hence I started working on a simple implementation for each one of them. I have now put together all of them in a single project on GitHub. I ensured that they all have the same set of procedures during their run. Some of the items I wanted to ensure was:

Same input array
Same number of iterations. Each iteration having the same input
Each algo being timed the exact same way as another

Some of the algorithms being tested were:

How did we ensure Equality?

Created a simple base class for all algorithms: AlgoStopwatch
- Responsible for benchmarking everything
- Provide a function called doSort() that would allow derived classes to implement their algorithm
- Ensures that every algorithm has a name and description - to help us distinguish
Another class to help manage the testing of all the algorithms: AlgoDemo
- All instances are created here for the algorithms
- The input array is provided by this class to all algorithms

Code

As usual the code for the project is available here:

https://github.com/abhi1010/Algorithms

It can be run using Visual Studio without any changes.

Numbers

Looking at the numbers below, it may be hard to compare the actual values. Hence I decided to normalize them by calculating how much time will be required to sort 100 numbers using the same rate as the actual numbers. They are provided for all algorithms on the right-most column.

Merge Sort	# of Items in Array	Time Taken	Average for 100 numbers
Random	10	0.047464	0.47464
	1K	5.41906	0.541906
	1M	8444.11	0.844411
Sorted	10	0.027155	0.27155
	1K	4.47016	0.447016
	1M	6323.05	0.632305

### Merge Sort 2	# of Items in Array	Time Taken	Average for 100 numbers
Random	10	0.033668	0.33668
	1K	3.89374	0.389374
	1M	7076.04	0.707604
Sorted	10	0.019034	0.19034
	1K	2.7833	0.27833
	1M	4664.16	0.466416

### [Insertion Sort](http://codersdigest.wordpress.com/2012/09/18/insertion-sort/)	# of Items in Array	Time Taken	Average for 100 numbers
Random	10	0.006095	0.06095
	1K	0.369859	0.0369859
	1M	323.878	0.0323878
Sorted	10	0.005022	0.05022
	1K	0.11696	0.011696
	1M	122.427	0.0122427

### [Heap Sort 1](http://codersdigest.wordpress.com/2012/10/17/heap-sort/)	# of Items in Array	Time Taken	Average for 100 numbers
Random	10	0.013543	0.13543
	1K	3.22043	0.322043
	1M	4770.14	0.477014
Sorted	10	0.007507	0.07507
	1K	0.625425	0.0625425
	1M	633.142	0.0633142

### [Heap Sort 2](http://codersdigest.wordpress.com/2012/10/17/heap-sort/)	# of Items in Array	Time Taken	Average for 100 numbers
Random	10	0.019352	0.19352
	1K	3.86284	0.386284
	1M	8914.22	0.891422
Sorted	10	0.011289	0.11289
	1K	3.49712	0.349712
	1M	6661.45	0.666145

### [Heap Sort 3](http://codersdigest.wordpress.com/2012/10/17/heap-sort/)	# of Items in Arraytrong>	Time Taken	Average for 100 numbers
Random	10	0.016266	0.16266
	1K	0.968032	0.0968032
	1M	900.004	0.0900004
Sorted	10	0.012845	0.12845
	1K	3.08637	0.308637
	1M	3839.23	0.383923

### [QuickSort](http://codersdigest.wordpress.com/2012/09/22/quick-sort/)	# of Items in Array	Time Taken	Average for 100 numbers
Random	10	0.072972	0.72972
	1K	2.74698	0.274698
	1M	4640.77	0.464077
Sorted	10	0.042773	0.42773
	1K	1.84335	0.184335
	1M	2473.42	0.247342

### [Counting Sort](http://codersdigest.wordpress.com/2012/09/11/counting-sort/)	# of Items in Array	Time Taken	Average for 100 numbers
Random	10	0.022982	0.22982
	1K	1.21822	0.121822
	1M	1823.85	0.182385
Sorted	10	0.026815	0.26815
	1K	1.19146	0.119146
	1M	1612.58	0.161258

### [Radix Sort](http://codersdigest.wordpress.com/2012/09/13/radix-sort/)	# of Items in Array	Time Taken	Average for 100 numbers
Random	10	0.033351	0.33351
	1K	3.22004	0.322004
	1M	5650.9	0.56509
Sorted	10	0.020659	0.20659
	1K	3.26273	0.326273
	1M	5683.91	0.568391

Coder’s Digest

Heap Sort vs Merge Sort vs Insertion Sort vs Radix Sort vs Counting Sort vs Quick Sort

How did we ensure Equality?

Code

Numbers

Merge Sort