Odd Even Sort

Best-Case time complexity - O(n)

Worst-Case time complexity - O(n^2)

Worst-case space complexity - O(1)

Does Bubble Sort, but on odd-indexed pairs, and then even-indexed pairs. This allows it to be multithreaded.

It is still inefficient. It is also possible to mix this with Cocktail Sort.

See Bubble Sort