Comparison Based Sorting algorithm – Computer Science Stack Exchange


Suppose an algorithm has access to a 3-ary comparison oracle for real numbers. That is operator B(x, y, z) returns a sorted permutation of xyz. Formulate and prove a lower-bound for any sorting algorithm that is only allowed to use queries to this comparison oracle to sort the input array.