Sorting an Array Using the Topological Sort of Corresponding Comparison Graph
Engineering
B.S. Computer Science, B.A. Mathematics
(Non-technical) The quest for efficient sorting is ongoing, and traditionally it deals with a linear algorithm on arrays. In this paper we will explore strategies to sort using graphs and achieve a sorting algorithm on par with mainstream sorting algorithms. We will state many theorems reflecting specific properties required for our method of sorting.
(Technical) The quest for efficient sorting is ongoing, and we will explore a strategy to sort employing comparison graphs. We use the topological sort of comparison graphs to map a graph to a linear domain, and we can manipulate our graph such that the topological sort is the sorted array. There exist many relations between Hamiltonian paths and topological sorts in comparison graphs which we take advantage of to achieve a Divide-and-Conquer algorithm that runs in $O(n log n)$ time which is at the lower bound of all sorting algorithms. Furthermore, using graphs as a sorting data structure can prove to be more efficient than multiple arrays since arcs can hold immense amounts of information for their costs.
