[RESEND PATCH v2 2/5] lib/sort: Use more efficient bottom-up heapsort variant

2019-03-19 Thread George Spelvin
This uses fewer comparisons than the previous code (approaching half as many for large random inputs), but produces identical results; it actually performs the exact same series of swap operations. Specifically, it reduces the average number of compares from 2*n*log2(n) - 3*n + o(n) to n*log2(n)

[PATCH v2 2/5] lib/sort: Use more efficient bottom-up heapsort variant

2019-03-15 Thread George Spelvin
This uses fewer comparisons than the previous code (approaching half as many for large random inputs), but produces identical results; it actually performs the exact same series of swap operations. Specifically, it reduces the average number of compares from 2*n*log2(n) - 3*n + o(n) to n*log2(n)