preprint · arXiv (Cornell University) · 2020
Sorting an Array Using the Topological Sort of a Corresponding\n Comparison Graph
Cited by 0Open access
Abstract
The quest for efficient sorting is ongoing, and we will explore a graph-based\nstable sorting strategy, in particular employing comparison graphs. We use the\ntopological sort to map the comparison graph to a linear domain, and we can\nmanipulate our graph such that the resulting topological sort is the sorted\narray. By taking advantage of the many relations between Hamiltonian paths and\ntopological sorts in comparison graphs, we design a Divide-and-Conquer\nalgorithm that runs in the optimal $O(n \\log n)$ time. In the process, we\nconstruct a new merge process for graphs with relevant invariant properties for\nour use. Furthermore, this method is more space-efficient than the famous {\\sc\nMergeSort} since we modify our fixed graph only.\n
Cite this paper
Behera, B. (2020). Sorting an Array Using the Topological Sort of a Corresponding\n Comparison Graph. arXiv (Cornell University). https://doi.org/10.48550/arxiv.2009.00098
Behera, Balaram. “Sorting an Array Using the Topological Sort of a Corresponding\n Comparison Graph.” arXiv (Cornell University), 2020, https://doi.org/10.48550/arxiv.2009.00098.
Behera, Balaram. 2020. “Sorting an Array Using the Topological Sort of a Corresponding\n Comparison Graph.” arXiv (Cornell University). https://doi.org/10.48550/arxiv.2009.00098.
Behera, B. (2020) ‘Sorting an Array Using the Topological Sort of a Corresponding\n Comparison Graph’, arXiv (Cornell University). Available at: https://doi.org/10.48550/arxiv.2009.00098.
@misc{behera2020sorting,
title = {{Sorting an Array Using the Topological Sort of a Corresponding\n Comparison Graph}},
author = {Behera, Balaram},
journal = {arXiv (Cornell University)},
year = {2020},
doi = {10.48550/arxiv.2009.00098}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.