This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 2.5 License.
Conceptually, this algorithm operates by maintaining two lists; one that is sorted and another unsorted one that contains items not yet examined by the algorithm. Initially, the sorted list is empty, and the unsorted list contains the original list passed as input to the algorithm. During each iteration, the algorithm removes one item from the unsorted list and inserts it into the appropriate location in the sorted list. It then terminates when there are no more items left in the unsorted list.
If the lists are stored as arrays, inserting an item into the sorted list involves both locating the appropriate insertion point and then shifting over existing values in order to make room for the new one. A typical implementation, illustrated in the code below, involves using a single array for both the sorted list and the unsorted list. Specifically, the first half of the array, represents the sorted list, while the later half of the array represents the unsorted list. The next item selected for insertion into the sorted list is then always the item in the unsorted list that lies directly on the boundary of the two.
The code uses a linear search, starting at the end of the sorted list, in order to find the appropriate insertion point. It combines this linear search with the shifting of the contents of sorted list. For the i-th item being inserted into the sorted list, this linear search/shift step involves, in the worst case, (i-1) comparisons/shifts. Thus, for a list of N items, if we experience the worst case for each of the inserted items, N(N-1)/2 comparisons/shifts are required. This gives the algorithm a time complexity of O(n2), like that of both Bubble sort and Selection sort. However, insertion sort tends to be greatly more efficient than both of these.
![[Valid RSS]](/renma/images/valid-rss.png "Validate my RSS feed")
