Quicker Sort? Implementing generic linear time sorting
Established generic sorting is based on comparison and is known to have a lower bound of O(n log n). In a recent paper1 Fritz Henglein sets out an approach based on discrimination which has a lower bound of O(n), a fundamental improvement to the state-of-the-art. In this talk Haskell and Scala implementations of generic linear time sorting, based on this paper, will be presented. Performance measurement methodology and the initial, encouraging results will be discussed.
Academic research can often be intimidating, and bridging the gap between paper and implementation can seem like a big task. In this talk the speaker will share their perspective on this process.
The talk seeks to demonstrate that composition can yield fundamental insights, that research is more accessible than people may think, and to show interesting implementation details of the algorithm by comparing and contrasting Scala and Haskell.
Pre-Requisites: Familiarity with Haskell and/or Scala syntax, and garden variety sorting algorithms.
References: Various papers on the topic are widely available, of which the two most relevant are, 1 Henglein, Fritz. “Generic top-down discrimination for sorting and partitioning in linear time.” Journal of Functional Programming 22.03 (2012): 300-374. 2 Henglein, Fritz, and Ralf Hinze. “Sorting and Searching by Distribution: From Generic Discrimination to Generic Tries.” Programming Languages and Systems: 11th Asian Symposium, APLAS 2013, Melbourne, VIC, Australia, December 9-11, 2013. Proceedings. Springer International Publishing, 2013.