Tree Sort

We can sort a given set of $n$ numbers by first building a binary search tree consisting of these numbers. Suppose we use insert to insert the numbers one by one. We then use inorder_walk to print them in order. What is the worst-case and best-case running times of this sorting algorithm respectively?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def insert(T,z):
   'inserts a node z onto a binary search tree T'
   y = None
   x = T.root
   while x != None:
      y = x
      if z.key < x.key:
         x = x.left
      else:
         x = x.right
   z.p = y
   if y == None:
      T.root = z
   elif z.key < y.key:
      y.left = z
   else:
      y.right = z

1
2
3
4
5

def inorder_walk(x):
   if x != None:
      inorder_walk(x.left)
      print x.key
      inorder_walk(x.right)