mbox series

[v2,0/2] stdlib: Optimize number of calls to comparison function in qsort

Message ID 20231205032207.3183789-1-visitorckw@gmail.com
Headers
Series stdlib: Optimize number of calls to comparison function in qsort |

Message

Kuan-Wei Chiu Dec. 5, 2023, 3:22 a.m. UTC 
  The current heapsort implementation in the siftdown function follows
the standard textbook version, necessitating two comparisons at each
level. Transitioning to the Bottom-up heapsort version allows us to
decrease the required comparisons to just one per level. On average,
this modification significantly reduces the comparison count from
2nlog2(n) - 3n + O(n) to nlog2(n) + 0.37*n + O(n).

Refs:
  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://doi.org/10.1016/0304-3975(93)90364-Y

Changes from v1:
* Use a more concise title.
* Correct the error in asymptotic notation from little-o to big-O.
* Adjusted the factor in tst-qsort5 from 4.5 to 3.5.

Kuan-Wei Chiu (2):
  stdlib: Optimize number of calls to comparison function in qsort
  stdlib: Adjust the factor in tst-qsort5

 stdlib/qsort.c      | 36 ++++++++++++++++++------------------
 stdlib/tst-qsort5.c |  2 +-
 2 files changed, 19 insertions(+), 19 deletions(-)