Skip to main content
Contents Index Dark Mode Prev Up Next \(
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Section 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})\text{.}\)
A merge sort is
\(O(n \log n)\text{,}\) but requires additional space for the merging process.
A quick sort is
\(O(n \log n)\text{,}\) 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.
