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:

*Stable sort*. Recall that a stable sort will leave identical keys in the same relative position in the sorted output. Insertion sort is the only algorithm covered that is stable.*Space*. An in-place sort does not require any extra space to accomplish its task. Both insertion sort and shell sort are in- place sorts. Quicksort requires stack space for recursion and therefore is not an in-place sort.*Tinkering*with the algorithm considerably reduced the amount of time required.*Time*. The time required to sort a dataset can easily become astronomical (Table 1-1). Table 2-2 shows the relative timings for each method. The time required to sort a randomly ordered dataset is shown in Table 2-3.*Simplicity*. The number of statements required for each algorithm may be found in Table 2-2. Simpler algorithms result in fewer programming errors.

method | statements | average time | worst-case time |
---|---|---|---|

insertion sort | 9 | O(n^{2}) |
O(n^{2}) |

shell sort | 17 | O(n^{7/6}) |
O(n^{4/3}) |

quicksort | 21 | O(n lg n) |
O(n^{2}) |

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 |