Adding one item to a binary search tree is on average an O(log n) process (in big O notation).

Expected O(n log n) time can however be achieved by shuffling the array, but this does not help for equal items.

Using such a tree, the algorithm has an O(n log n) worst-case performance, thus being degree-optimal for a comparison sort.

On most common platforms, this means that heap memory has to be used, which is a significant performance hit when compared to quicksort and heapsort[citation needed].

When using a splay tree as the binary search tree, the resulting algorithm (called splaysort) has the additional property that it is an adaptive sort, meaning that its running time is faster than O(n log n) for inputs that are nearly sorted.