Sorting

A sequential search is O(n)$O(n)$ for ordered and unordered lists.

A binary search of an ordered list is O(logn)$O(\log n)$ in the worst case.

Hash tables can provide constant time searching.

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

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

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

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