RUN TIMES FOR SORT METHODS

BinSearchTree Sort

In Chapter 12, study the averageTime (n) and worstTime (n) for the sort algorithms we have covered. We can easily add two new ones: BinSearchTree Sort and AVLTree Sort. They work the same as (Red-Black) Tree Sort except that the elements are added to a BinSearchTree or AVLTree.

Write down the Big O estimates in each case:

                                    averageTime (n)   worstTime (n)

Insertion Sort

Merge Sort

(Red-Black) Tree Sort

Heap Sort

BinSearchTree Sort

AVLTree Sort

Quick Sort