If there were no complex ADT List structures with O(1) Lookup, there would still be sort. No Table doubling required.
Recently got amused with Stack Sort while doing what I do. So if there were no abstract Non-continuous List structure (Not Linked List) and you wanted to sort your stacks, which I recently found useful somewhere low-level, this is it.
What better language to leverage Linked lists for sorting where Lists really do not exist, to implement stack sort. So this is StackSort in Elixir:
