Mentions légales du service

Skip to content

WIP: Added heap sort, tested against aseba_comb_sort and C++ std::sort

SHERMAN David requested to merge github/fork/shilingwang/natives-heapsort into master

Created by: shilingwang

As described in issue #674, the complexity of math.sort (comb sort) is worst case O(n^2) and best case O(n log(n)). Here I implement heap sort, which should be worst-case O(n log(n)) complexity. The test results (Linux x86_64, g++ 5.4.0, i7-5600U CPU, no optimisation) for comb sort, heap sort and c++ std::sort show that when the data are in random order, the three implementations are not much different and std::sort and comb sort are always a little bit better than heap sort. When the data are already in sorted order without duplication, heap sort is slower than the other two (no more than double). However, when the data is const, heap sort is much faster than comb sort (10 times or more).

Merge request reports

Loading