If you continue browsing this website, you agree to our policies:

x
Completion requirements

This page explains and implements selection sort, bubble sort, merge sort, quick sort, insertion sort, and shell sort.

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

A binary search of an ordered list is $O(\mathrm{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({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\mathrm{log}n)$, but requires additional space for the merging process.

A quick sort is $O(n\mathrm{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.