fastest sorting in functional style

Question

As an undergrad, I studied O(n log n) algorithms for sorting and proofs that we cannot do better for the general case when all we can do is compare 2 numbers. That was for a random access memory model of computation. I want to know if such theoretic lowerbounds exists for functional style(referentially transparent) programs. Let us assume that each beta reduction counts as one step, and each comparison counts as one step.

Answer 1

So let us assume that you agree with the proof that we cannot do better than (n*log n) in a general case where the only thing we have is a comparison.

So the question is whether we can show that we can do the same without side effects.

One way to do that uses the idea that if you can build an immutable binary search tree in O(n*log n) and then infix-traverse it (can be done in O(n)), then we would have a sorting algorithm.

If we can go through all items and add every item to a balanced immutable (persistent) tree in O(log n) it would give us O(n*log n) algorithm.

Can we add to a persistent binary tree in O(log n)? Sure, there are immutable variants of balanced binary search trees with O(log n) insert in every reasonable implementation of persistent data structure library.

To get an idea why it is possible, imagine a standard balanced binary search tree as e.g. red-black tree. You can make immutable version of it by following the same algorithm as for the mutable one, except whenever pointers or color change, you need to allocate a new node and consequently all of its parents to the root (while simultaneously transforming them too if necessary). Side branches that do not change get reused. There are at most O(log n) affected nodes, so at most O(log n) operations (including allocations) per insertion. If you know red-black, you can see that there are no other multipliers to this except for constants (for rotations you can get a few extra allocations for affected siblings, but that still remains a constant factor).

This - quite informal - demonstration can give you an idea that a proof for O(n*log n) for sorting without side effects exists. However, there are a few more things that I left out. E.g. allocation is considered to be O(1) here, which may not be a case always, but that would get too complex.