Insertion Sort
Introducion Input: A sequence of n numbers ( a 1 , a 2 . . . , a n ) Output: A permutation (reordering) ( a' 1 , a' 2 , . . . , a' n ) of the input sequence such that a' 1 < a' 2 <. . . < a' n . The numbers that we wish to sort are also known as the keys . Although conceptually we are sorting a sequence, the input comes to us in the form of an array with n elements. Sorting a hand of cards using insertion sort. We start with insertion sort, which is an efficient algorithm for sorting a small number of elements. Insertion sort works the way many people sort a hand of playing cards. We start with an empty left hand and the cards face down on the table. We then remove one card at a time from the table and insert it into the correct position in the left hand. To find the correct position for a card, we compare it with each of the cards already in the hand, from right to left. At all times, the cards held in the left hand are s...