If the initial array were given in sorted order, the insertion of the kth record would require one comparison and no insertions. The total time would be O(n - 1). If the initial array were given in reverse sorted order, the insertion of the kth record would require (k - 1) comparisons, and the kth record would have to be inserted at the top of the array. To accomplish this, each of the (k - 1) records must be moved down one element. The total time will be the time for the 1 + 2 + ?/FONT> ?/FONT> ?/FONT> + (n ?1) comparisons, plus the time for the 1 + 2 + ?/FONT> ?/FONT> ?/FONT> + (n ?1) shifts down. Consequently, the total time is O(n2). This represents the worst case. Again we see that the time can vary with n2 for large n. The insertion sort, like the bubble sort, performs better the closer the initial data is to being sorted. If each of the n! possible initial orderings of the array with n distinct entries is equally likely to occur, then the average time for all three of the sorts considered so far is also O(n2).
In the three implementations for the sorting algorithms, it was assumed that the interchanges taking place were actually interchanges of records. When records are large, it takes appreciably more time to move a record than it does to move a single pointer to the record. Consequently significant amounts of time can be saved by keeping an array, p, of indexes or pointers to the records. The entries of this array can then be kept in order, so that p[i] indexes or points to the ith record in sorted order. Interchanging indexes or pointers takes less time than for records but uses more memory (which is an added expense). This is another example of trading time for storage. In the procedures shown for maximum entry sort, bubble sort, and insertion sort, the interchange operations would then apply to the array p, and the comparison operations would apply to the actual records indexed or pointed to by i.