Sorting Algorithms

I don't know of any sequential data structure for which both insertion and random access (which is needed for the binary search you're describing) are O(1).

As long as they're under O(n) it helps... they could be log(n) or n^0.5 and it would be better than doing it linearly.



If it was in a tree with fast insertion you'd get both in O(log(n)) for example, as long as the height of the tree ~ log(n).


Then you go through n points with O(log(n)) to insert each, overall O(n logn), which matches single threaded quicksort. Not sure how feasible it is to make a thread safe tree for insertion only. If it is possible then you should get O(log n) sorting with n processors.