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

methodstatementsaverage timeworst-case time
insertion sort 9 O(n2) O(n2)
shell sort 17 O(n1.25) O(n1.5)
quicksort 21 O(n lg n) O(n2)

Table 2-3: Sort Timings

countinsertionshellquicksort
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