Since one usually reports the order of growth for an algorithm as the worst-case order of growth, the insertion
sort has a theta of n2, or ??(n2). If one computes the average case order of growth for the insertion sort, one also
finds a quadratic equation; it??™s just somewhat smaller, since on average each new element will be compared with
only half of the elements already sorted. So we say the performance of the insertion sort is ??(n2).
Merge sort??”An example of order of growth of n(lg n)??” Q(n lg n)
Another algorithm for sorting numbers uses recursion, a technique we will discuss in more detail shortly,
to divide the problem into many smaller problems before recombining the elements of the full solution. First,
this solution requires a routine to combine two sets of sorted numbers into a single set.
Imagine two piles of playing cards, each sorted from smallest to largest, with the cards face up in two piles,
and the two smallest cards showing. The merge routine compares the two cards that are showing, and places the
smaller card face down in what will be the merged pile. Then the routine compares the two cards showing after
the first has been put face down on the merged pile. Again, the routine picks up the smaller card, and puts it
face down on the merged pile.
Pages:
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60