AN EFFICIENT ALGORITHM FOR SORTING A SET OF ELEMENTS WITH PARENT-CHILD RELATIONSHIPS

Abstract

A real world system may have a database table of records with parent-child relationships. The records may not be inserted into the table in family tree order. This paper proposes an efficient algorithm to solve the problem of sorting a list of elements with parent-child relationships that correspond to all the records in the database table. It is assumed that all the records are loaded into memory as a list of elements. The algorithm first creates a list S with the first element storing representatives of root elements and each other element storing a representative set of children of an element in the input list. The list S forms a set of trees of input elements. Then, each input element is added to the output sorted listed by performing a depth-first search on each tree. The algorithm takes O(nlog(n)) time and O(n) space to solve the problem where n is the number of elements. The algorithm takes about 154 (seconds) to sort 2,441,405 elements using a laptop with an Intel(R) Core(TM) i7-4510U CPU @ 2.00GHz 2.60 GHz processor, and 8 GB of RAM.