Imagine you have a randomly sorted poker hand which you need to reorganize from left to right in the traditional fashion of 2,3,4,5…etc up until Jack,Queen,King,Ace. Most people, without thinking, will likely grab an individual card and move it to the correct spot and repeat this action until they achieve a “sorted” hand – this is called “insertion sort” by computer scientists and the procedure goes something like this:
1.) Take the first card in your hand. Lets say its a queen.
2.) Look at the next card in your hand. Is it less than a Queen? If so, skip it and look at the next card after that.
3.) Keep repeating this procedure until you find a King or Ace and then stop. Insert the Queen card prior to the King or Ace you encountered.
4.) Working from left to right, perform this operation over and over again until you reach the last card, which should be an Ace by the time you are done.
5.) If you are attempting to sort an Ace, you will keep searching until you reach the end of the hand – in many programming languages, an Array is terminated by a null character which signals you are holding the highest card in the set currently.
So now we have an idea of what Insertion Sort is all about.
However, in Computer Science – knowing how to implement an algorithm is only the beginning of the process. When thinking about any algorithm such as Insertion-Sort, we immediately have to think about a list of common questions which will be asked in any programming interview and should arise:
- How fast is this method of sorting?
- How much space does it take up to perform insertion sort?
- Is there a faster way to sort than insertion sort?
Anyone who has ever studied complexity analysis will understand the importance of these questions – because, unlike in the world of poker, in the world of computer science it is common to sort millions of records instead of only a single handful. At very vast scales…such as those performed in datacenters owned by Amazon, Google and Facebook on a daily basis, algorithms matter…they really *really* matter. A simple adjustment can exponentially increase the speed at which an operation is performed and becoming conversational in the “craft” of complexity analysis (nerd speak for “analyzing algorithms generally with the intent to make them faster”) is a critical skill.
So returning to the three major questions which we are asking of Insertion-Sort.
“How fast is this method of sorting.”
Well – there are a couple ways to approach this. Lets say I am handed a stack of cards which are already completely sorted except for one out of place card at the very end – the Ace is in the second to last position instead of the last position. I would have to tediously iterate over every card in the deck and compare it to every other card in the deck to check if it is “in place” one at a time before finally reaching that single “misplaced” Ace and realizing that I have found an unsorted card.
In short – if I have 52 cards, I would have to compare each of those 52 cards to every other card in order to see if it is out of place.That isn’t very efficient – and Computer Scientists would say the algorithm has a complexity of “n-squared.”
“How much space does it take to perform Insertion-Sort”
Technically, looking at the problem, it seems that we don’t really need any more space than what is provided by the cards in our hand – in computer science speak this is an “in-place” sorting algorithm because no extra space is needed. In other algorithms, it might be necessary to have a sort of “buffer” in which we do our busy-work before arriving at a final solution. Insertion-Sort does not require such a bugger.
“Is there a faster way to sort than insertion sort?”
The answer to that question is “yes.” Over the years, numerous sorting algorithms have been developed to solve the sorting problem. Sorting has been recognized as a central problem for many, many business applications where large data is a factor and a quick search on Wikipedia will turn up at least a dozen different variants of the sorting process.
With it’s sorting speed of n-squared, Insertion-Sort is rated as the 3rd slowest type of sorting procedure. The only way you could do worse is to have what is known as an “exponential” sorting speed such as 5 to the N or, if you have really done something wrong, N! or “n-factorial.”
