Insertion Sort

Sep 17, 2012 · Comments
code sorting algo c++

Insertion Sort has the following properties:

It works by moving elements one at a time
Works really well for small data sets
Consider going with this when the input data may already be sorted or partially sorted
The may not have to move the elements around, thereby saving precious cycles
Stable sort
Keeps the original order of elements with equal values

Testing Notes

Had a very interesting time testing my code. I knew that swapping takes time. std::swap takes particularly longer. I disabled that from the beginning itself
Even more interesting was how I thought of fixing my code which was running slowly
Initially even running an array of size 1K was taking about 4s so I just made a minor change to remove “– insertIndex ;” altogether and do the calculation in the previous line itself. That did the trick. Otherwise the code was taking hours and hours for 1M array size so I had to stop running it.
I even tried improving the code a bit futher by ensuring that I do not call insertIndex-1 many a times but that didn’t really help - in fact made it worse again
Sorted runs will run much faster because there’s no work to be done in those cases
Would be a nice algo to use if your data is mostly sorted

As usual the code is available here: