2017 LLVM Developers’ Meeting: A. Kumar “Introsort based sorting function for libc++ ”

LLVM
16.2K subscribers
<__slot-el>
<__slot-el>
1.1K views 7 years ago
http://www.LLVM.org/devmtg/2017-10/ — Introsort based sorting function for libc++ - Divya Shanmughan and Aditya Kumar Slides: http://llvm.org/devmtg/2017-10/slides... — The sorting algorithm currently employed in libc++ library uses quicksort with tail recursion elimination, as a result of which the worst case complexity turns out to be O(N^2), and the recursion stack space to be O(LogN). This talk will present the work done to reduce the worst case time complexity, by employing Introsort, and by replacing the memory intensive recursion calls in the quicksort with stacks . Introsort is a sorting technique, which begins with quicksort and when the recursion depth (or depth limit) goes beyond a threshold value, then it switches to Heapsort . — Videos Filmed & Edited by Bash Films: http://www.BashFilms.com ...more
...more
2017 LLVM Developers’ Meeting: A. Kumar “Introsort based sorting function for libc++ ”
8Likes
1,143Views
2017Oct 31
http://www.LLVM.org/devmtg/2017-10/ — Introsort based sorting function for libc++ - Divya Shanmughan and Aditya Kumar Slides: http://llvm.org/devmtg/2017-10/slides... — The sorting algorithm currently employed in libc++ library uses quicksort with tail recursion elimination, as a result of which the worst case complexity turns out to be O(N^2), and the recursion stack space to be O(LogN). This talk will present the work done to reduce the worst case time complexity, by employing Introsort, and by replacing the memory intensive recursion calls in the quicksort with stacks . Introsort is a sorting technique, which begins with quicksort and when the recursion depth (or depth limit) goes beyond a threshold value, then it switches to Heapsort . — Videos Filmed & Edited by Bash Films: http://www.BashFilms.com

LLVM

16.2K subscribers