Re: [PATCH] Implement introsort for qsort

[Kuan-Wei Chiu <visitorckw@gmail.com>]

On Sun, Dec 31, 2023 at 03:59:40AM +0800, Kuan-Wei Chiu wrote:
> Enhances the qsort implementation by introducing introsort to address
> the worst-case time complexity of O(n^2) associated with quicksort.
> Introsort is utilized to switch to heapsort when quicksort recursion
> depth becomes excessive, ensuring a worst-case time complexity of
> O(n log n).
> 
> The heapsort implementation adopts a bottom-up approach, significantly
> reducing the number of required comparisons and enhancing overall
> efficiency.
> 
> Refs:
>   Introspective Sorting and Selection Algorithms
>   David R. Musser
>   Software—Practice & Experience, 27(8); Pages 983–993, Aug 1997
>   https://dl.acm.org/doi/10.5555/261387.261395
> 
>   A killer adversary for quicksort
>   M. D. McIlroy
>   Software—Practice & Experience, 29(4); Pages 341–344, 10 April 1999
>   https://dl.acm.org/doi/10.5555/311868.311871
> 
>   BOTTOM-UP-HEAPSORT, a new variant of HEAPSORT beating, on an average,
>   QUICKSORT (if n is not very small)
>   Ingo Wegener
>   Theoretical Computer Science, 118(1); Pages 81-98, 13 September 1993
>   https://dl.acm.org/doi/10.5555/162625.162643
> 
> Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
> ---
> To assess the performance of the new introsort and the old quicksort in
> worst-case scenarios, we examined the number of comparisons required
> for sorting based on the paper "A killer adversary for quicksort."
> 
> Before the patch:
> n = 1000,  cmp_count = 100853
> n = 2000,  cmp_count = 395991
> n = 3000,  cmp_count = 885617
> n = 4000,  cmp_count = 1569692
> n = 5000,  cmp_count = 2448183
> n = 6000,  cmp_count = 3521140
> n = 7000,  cmp_count = 4788493
> n = 8000,  cmp_count = 6250342
> n = 9000,  cmp_count = 7906610
> n = 10000,  cmp_count = 9757353
> 
> After the patch:
> n = 1000,  cmp_count = 27094
> n = 2000,  cmp_count = 61500
> n = 3000,  cmp_count = 100529
> n = 4000,  cmp_count = 136538
> n = 5000,  cmp_count = 182698
> n = 6000,  cmp_count = 221120
> n = 7000,  cmp_count = 259933
> n = 8000,  cmp_count = 299058
> n = 9000,  cmp_count = 356405
> n = 10000,  cmp_count = 397723
> 
Hi Brian,

Thank you for sharing the information; I will take the time to review
the details you provided.

I noticed that your responses have been directed solely to the newlib
mailing list. For our future correspondence, could you please include
me or CC me? This would greatly help me in staying informed.

I appreciate your assistance.

Best regards,
Kuan-Wei Chiu