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, as illustrated in Figure 2.1.  At all times, the cards held in
the left hand are sorted, and these cards were originally the top cards of the pile on the table.

INPUT: provided in an array of size n.
Algorithm: (Pseudo code)
(Since the first location is sorted by itself, the loop starts from 2.)

for i = 2 to n do
    Ensure that the first i locations
    are in sorted order
end

for (i = 1; i < n; i++) 
{ 

   j = i; 
   target = v[i]; 
   while (j > 0 && target < v[j-1]) 
   { 

     v[j] = v[j-1]; 
     j--;

    }

    v[j] = target;

} 

Click here to see figure 2.2 on page 17 of text book by Cormen, Leiserson, Rivest and Stein. (Sort the array A={5, 2, 4, 6, 1, 3})  Click here to see how to sort.

Analysis:
Time:
The number of data movement = 3 when you swap two numbers.
The number of instruction = 1 when you do comparison.
 

		Running Time	# of comparisons
i=2	1st iteration	4 (1 for comparison, 3 for swapping)	1
i=3	2nd iteration	2 x 4	2
:
:
i=m+1	mth iteration	m x 4	m
:
:
i=n	(n-1)th iteration	(n - 1) x 4	n -1
		Total = (1 +2 +3 + ...+(n - 1)) x 4  = O(n2)

Space:

• 1 for i
• 1 for j
• 1 for T (temp for swapping)
• You need 3 spaces  (= O(1) constant growth rate)