Insert Sort
Introduction
The insert sort algorithm is both simple and efficient. It works by looking at each item in turn (starting from the 2nd item and then shifting all the items (on its left) that are larger than it to the right and then inserting the new item into the gap created. This ensures that the items are always in the correct order up to the current point the sort has reached. If the item to be checked is the largest item (that is everything to its left is “smaller” ) then we just move onto the next item in the set.
The algorithm requires more work in the swap process, because unlike the bubble sort, the insert sort may require that a number of items be moved, before the new item can be inserted. Also to find out which items need to be shifted to the right, the new item must be compared with all the neighbours to the left until a neighbour that is “smaller” has been found or the beginning (leftmost point) has been reached. In the extreme circumstance that the current item to be sorted is the “smallest” then every item to its left must be shifted one space along so that the new item can be put in the correct place.
However the insertion sort is extremely efficient at handling pre-sorted lists where new items need to be added and sorted into the existing set, as unlike most sort algorithms it will use the current sorted state of the set to its advantage. Even starting from the beginning of a sorted list and working it’s way through, the insert sort algorithm only needs to compare the first neighbour to the left of each item to confirm that the item we are currently checking is in the correct order (that is greater or equal to its immediate neighbour on the left). So very quickly the insert algorithm reaches the first item that is out of sort order.
It is also considered to be the nearest algorithm to how we sort a large number of items manually (for example sorting a deck of playing cards).
Most sort algorithms work on the principle that the set of data that needs to be sorted is “fixed” in time (the number of items to be sorted remains constant throughout the sort). Insert sort, on the other hand is quite capable of continuing to sort in new items as they arrive without adversely upsetting the current state of the sort. Suppose we have another computer system (or number of systems) that feeds data asynchronously to a sort algorithm, while the bubble, quick and network sorts, would all have to start from the beginning, the insert sort would just add the item to the end of the list and continue sorting using the same process.
Excellent work Tom 🙂