Comparison

In this section we will compare the sorting algorithms covered: insertion sort shell sort and quicksort. There are several factors that influence the choice of a sorting algorithm:



Table 2-2: Comparison of Sorting Methods
method statements average time worst-case time
insertion sort 9 O(n2) O(n2)
shell sort 17 O(n7/6) O(n4/3)
quicksort 21 O(n lg n) O(n2)

Table 2-3: Sort Timings
count insertion shell quicksort
16 39 Ás 45 Ás 51 Ás
256 4 969 Ás 1 230 Ás 911 Ás
4 096 1.315 sec .033 sec .020 sec
65 536 416.437 sec 1.254 sec .461 sec