Use of Tree-based Algorithms for Internal Sorting

Most of the large number of internal sorting algorithms are based on the use of arrays or linked lists. This report highlights the use of tree structures for internal sorting. It is shown that the ordered binary tree can be used very effectively for sorting data, whatever the initial ordering of the input may be. It is also shown that the B-Trees, normally used to process large files on disks, can also be effectively employed to sort data in main memory. In both cases, a simple inorder traversal of the tree can retrieve data in sorted order. Algorithms based on binary- and B-tree structure are compared with Quick Sort and Heap Sort algorithms in terms of times required to sort various input lists. Input lists of various sizes and degrees of 'presortedness' were used in the comparison tests. It is shown that the times required to build balanced ordered binary trees are the same as or less than the times required to sort the data using Quick Sort and always better than the times required..