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).
This patch reduces the worst case time complexity, by employing Introsort algorithm. 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 .As a result the worst case complexity reduces to O(NlogN)
Worked in collaboration with Aditya Kumar.