Binary tree sort implemented using a self balancing binary search tree takes O(n log n) time in the worst case but still it is slower than merge sort.

Category: QuestionsBinary tree sort implemented using a self balancing binary search tree takes O(n log n) time in the worst case but still it is slower than merge sort.
Editor">Editor Staff asked 4 weeks ago

Binary tree sort implemented using a self balancing binary search tree takes O(n log n) time in the worst case but still it is slower than merge sort.
 
(a) True
 
(b) False
 
My question is taken from Binary Trees topic in portion Binary Trees of Data Structures & Algorithms I
 
I got this question by my school principal while I was bunking the class.

1 Answers
Editor">Editor Staff answered 4 weeks ago

Correct choice is (a) True
 
The best explanation: The worst case performance of binary tree sort is O(n log n) when it is implemented using a self balancing binary search tree. Self balancing binary search trees perform transformations to balance the tree, which caused balancing overhead. Due to this overhead, binary tree sort is slower than merger sort.