Drop Sort

Average time complexity - O(3n^2 + 2n)

Best-Case time complexity - Θ(3n)

Worst-Case time complexity - Ω(4n^2 + 2n)

Worst-case space complexity - O(2)

Drop Sort is a lossy sorting algorithm that removes elements lower than the previous from the array. Every time it encounters a smaller element, it deletes it and shifts the entire array to the left.

Let's take the following array as an example:

4, 1, 5, 2, 3

Drop Sort would compare 4 and 1. 1 is the second item, and it is smaller, so it is removed.

4, 5, 2, 3

Next it would compare 4 with 5. 5 is greater, so it is fine. Then it compares 5 with 2. 2 is smaller, so it deletes it.

4, 5, 3

Next it compares 5 with 3. 3 is smaller, so it deletes it.

4, 5

The array we are left with is in sorted order, even though it is missing some elements.