Flash Sort

Average time complexity - O(n)

Best-Case time complexity - Θ(n)

Worst-Case time complexity - Ω(n)

Worst-case space complexity - O(?)

Flash Sort is a complicated algorithm that I don't really understand. It's about the estimation of the locations of elements.

All I know is what happens to the array each pass. So here it is. Let's start with the following array:

4, 1, 5, 2, 3

Here is what happens, pass-by-pass:

5, 1, 4, 2, 5

5, 1, 4, 3, 5

5, 2, 4, 3, 5

1, 2, 4, 3, 5

1, 2, 4, 3, 5

Then it calls Insertion Sort on the remaining, which would just swap 4 with 3, and your array is sorted.

1, 2, 3, 4, 5

I don't really know how this works. Apparently this homo sapien does. And so does this human.