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

Code

As usual the code is available here:

https://github.com/abhi1010/Algorithms

Numbers