There can be a total ordering on elements in a array.
We want to return an array such that only the ordering is changed.
\(\forall nm [array[n]>array[m] \leftrightarrow n>m]\)
Take the first two items. See if they are sorted. If they are not, swap them.
Then move to next pair, and do same.
Keep going until the end.
If the number of swaps was greater than 0, loop around again.
Worst case: \(O(n^2)\) comparisons and \(O(n^2)\) swaps. Average case: \(O(n^2)\) comparisons and \(O(n^2)\) swaps.
Best case: \(O(n)\) comparisons and \(O(1)\) swaps.
This is an in place algorithm.