7.10. Summary

• A bubble sort, a selection sort, and an insertion sort are $O(n^2)$ algorithms.

• A shell sort improves on the insertion sort by sorting incremental sublists. It falls between $O(n)$ and $O(n^2)$.

• A merge sort is $O(n\log n)$, but requires additional space for the merging process.

• A quick sort is $O(n\log n)$, but may degrade to $O(n^2)$ if the split points are not near the middle of the list. It does not require additional space.

You have attempted 1 of 1 activities on this page