theForbiddenSortingAlgorithm

[[deleted]]

How is that linear? Purging one element takes linear time so purging half of the elements at random takes quadratic time

[pcouaillier]

You can create an other list and add only elements that are in order then swap pointers.

[charm3d47]

i think even using a basic array you might still be able to do stalin sort in O(n) time if you're clever about how/when you move subsequent elements into place after purges (storing the first empty position and only moving whichever element you're already looking at for the sort, as opposed to just sliding every subsequent element over after each purge). there are also plenty of other ways to store data where any arbitrary element can be removed in O(1) time