Now that we have formulas to describe the worst case time efficiency of our sorting algorithms, we can see how the algorithms will perform as we increase the number of items to be sorted. First, let's review our formulas. Notice that the formulas for swaps have been converted to copies by multiplying by 3. This allows us to correctly compare Simple Sort with the other two sorts.

Algorithm Comparisons Copies
Simple Sort n * (n-1) n
Insertion Sort (n-1) + (n-2) + ... + 1 3 * [(n-1) + (n-2) + ... + 1]
Selection Sort (n-1) + (n-2) + ... + 1 3 * (n-1)

Using our formulas, we will compute the number of comparisons and copies needed to sort several lists of items. The number of items in each list increases by a power of ten.

Comparisons Required
# of Items Simple Sort Insertion Sort Selection Sort
10 90 45 45
100 9,900 4,950 4,950
1,000 999,000 499,500 499,500
10,000 99,990,000 49,995,000 49,995,000

From our table of comparisons, we can see two important facts. First, the Simple Sort always requires twice as many comparisons as the Insertion and Selection Sorts. This means we can rewrite the formula for these sorts as follows: (n * (n-1)) / 2. This expression is much easier to use than the summation (n-1) + (n-2) + ... + 1, especially when n is large.

Second, all three sorts require a tremendous number of comparisons as the number of items increases. In fact, we can see with the Simple Sort that the number of comparisons is very close to n2. Take another look at the formula you derived for the number of comparison the Simple Sort requires in the worst case. If we multiply the n into the parentheses, the formula becomes n2 - n. Now you see why our total comparisons is very near n2. You can also see why the number of comparisons needed is growing so quickly.

Copies Required
# of Items Simple Sort Insertion Sort Selection Sort
10 10 135 27
100 100 14,850 297
1,000 1,000 1,498,500 2,997
10,000 10,000 149,985,000 29,997

Now let's compare the number of copies each algorithm requires. Notice how quickly the number of copies required by the Insertion Sort is growing. This makes us suspect that the formula for the Insertion Sort contains an n2 term. In fact, the formula does contain such a term, but we must rewrite the formula to see it. Using the relationship we discovered earlier, we can replace the summation (n-1) + (n-2) + ... + 1 with (n * (n-1)) / 2 and simplify.

# of copies  =  3 * [(n-1) + (n-2) + ... + 1]
# of copies  =  3 * [(n * (n-1)) / 2] 
# of copies  =  (3 / 2) * [n * (n-1)] 
# of copies  =  (3 / 2) * [n2 - n]

The simplified formula shows the n2 term that we suspected. Notice that the other two formulas only have an n term rather than a n2 term. This is the reason that they grow slowly as the number of items increases.