summaryrefslogtreecommitdiff
path: root/tests/test_compact.cpp
diff options
context:
space:
mode:
authorArseny Kapoulkine <arseny.kapoulkine@gmail.com>2017-02-07 00:05:50 -0800
committerArseny Kapoulkine <arseny.kapoulkine@gmail.com>2017-02-07 00:05:50 -0800
commit2162a0d80c2ac29f835e09e0c5366cdc7a1c1a7d (patch)
tree35b95d20e7119696d6b964620e404960a28393fe /tests/test_compact.cpp
parent774d5fe9df07ce68ac45ecdfebe71508a611d759 (diff)
XPath: Simplify sorting implementation
Instead of a complicated partitioning scheme that tries to maintain the equal area in the middle, use a scheme where we keep the equal area in the left part of the array and then move it to the middle. Since generally sorted arrays don't contain many duplicates this extra copy is not too expensive, and it significantly simplifies the logic and maintains good complexity for sorting arrays with many equal elements nonetheless (unlike Hoare partitioning). Instead of a median of 9 just use a median of 3 - it performs pretty much identically on some internal performance tests, despite having a bit more comparisons in some cases. Finally, change the insertion sort threshold to 16 elements since that appears to have slightly better performance.
Diffstat (limited to 'tests/test_compact.cpp')
0 files changed, 0 insertions, 0 deletions