Tree Sort

Sort Type: Comparison-Based Sorting / Insert and Keep Sorting

Algorithm

Description:

Because of its structure records stored in a binary tree are already in sorted order if a traversal of the tree is made using an Inorder search technique.


Data holder: Something to hold the original unsorted records, like an array. If records are to be stored in a binary tree no other data structure is needed.

Technique:
  1. Insert each record into the binary tree using the standard binary tree InsertNode() function.
  2. Perform an Inorder tree traversal to list records in sorted order.


Analysis: Tree Sort runs in O(n log n) time.