Timeline for Vergesort — A runs-adaptive layer to enhance sorting algorithms
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 31, 2019 at 5:02 | answer | added | L. F. | timeline score: 1 | |
| Jul 25, 2017 at 15:04 | history | edited | Toby Speight | CC BY-SA 3.0 |
Fixed a small typo
|
| Jan 19, 2017 at 21:12 | comment | added | Morwenn | @Walter I like it more. Also, consistency with every other function in my recent libraries. I also do like to always specify the return type to make sure that I haven't just forgotten it (it happened...) :p | |
| Jan 19, 2017 at 20:59 | comment | added | Walter |
Btw, what's the point of your fancy auto foo() -> void { /* ... */ } syntax instead of simply void foo()? (also in C++14 I think you don't need the -> part).
|
|
| Jan 19, 2017 at 20:56 | comment | added | Morwenn | @Walter Right, that's a missed optimization I forgot to mention (but that was mentioned in the README a long time ago). I was too lazy to implement it (actually to think every case through) until there .____. | |
| Jan 19, 2017 at 20:54 | comment | added | Walter | I also think that reversing a descending run is unnecessary work: you could keep its order but account for that when merging. | |
| Jan 19, 2017 at 16:13 | comment | added | Morwenn | @Walter I fear that it wouldn't be as cache-friendly as the current merge strategy. The complexity of the merge strategy can't go below O(n log k) = O(n log log n) anyway, so it wouldn't help with complexity either :/ | |
| Jan 19, 2017 at 16:06 | comment | added | Walter | Wouldn't a heap-based merging be best? (with a min-heap on the sequences to be merged), see here | |
| Jan 18, 2017 at 21:25 | comment | added | Morwenn | @RichardHodges The full version is in cpp-sort, and there is a CMakeLists.txt to run the whole testsuite with the most recent g++ or clang++ with C++14. There aren't really individual tests for this specific algorithm. It's tested along with other algorithms. | |
| Jan 18, 2017 at 21:21 | comment | added | Richard Hodges | Is the complete implementation on github or similar, with test cases? (ideally with a CMakeLists.txt file ^^). Maybe that's a better place to start if we're looking to converge on the optimal solution? | |
| Jan 18, 2017 at 21:09 | comment | added | Morwenn | That said, this is a simplified version (no support for projections and proxy iterators, no fallback to pattern-defeating quicksort, etc...). I removed the extra features by hand before posting here, so I may have left a few typos :/ EDIT: it compiles fine and passes basic tests without a problem ^_^ | |
| Jan 18, 2017 at 21:07 | comment | added | Morwenn | @RichardHodges The complete version passes the testsuite of my cpp-sort library, which happens to be independently run through Valgrind and with gcc and clang's undefined behaviour sanitizers :) | |
| Jan 18, 2017 at 20:52 | comment | added | Richard Hodges | before we start, does it pass tests? | |
| Jan 18, 2017 at 16:39 | history | tweeted | twitter.com/StackCodeReview/status/821759004309393409 | ||
| Jan 17, 2017 at 20:37 | history | edited | Morwenn | CC BY-SA 3.0 |
Fix dumb typo in title
|
| Jan 17, 2017 at 20:18 | history | asked | Morwenn | CC BY-SA 3.0 |