Timeline for Heap selection sort in Java
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 28, 2015 at 19:17 | comment | added | maaartinus |
@coderodde Above I was wrong with "2.5 on average", it's actually 3. Doubling it by merging two consecutive runs should be trivial and so should be lower bounding the minimum run length. This could cut the overhead to something small, but the memory indirection remains. +++ I guess, you could make HSS stable by comparing lexicographically (value, position). +++There's been too many too smart people working on sorting.
|
|
| Jul 28, 2015 at 12:28 | comment | added | coderodde | Yeah, I know. Just like Dijkstra's smoothsort, HSS has impractically large constant factors. :( | |
| Jul 27, 2015 at 20:08 | comment | added | maaartinus |
@coderodde I replaced Run by long and got better numbers: Heap selection sort in 719 ms. ... Heap selection sort in 555 ms. (instead of 703 ms). Still too slow, probably because of the runs being short (2.5 on average) and maybe because of the memory indirection overhead.
|
|
| Jul 27, 2015 at 14:03 | comment | added | coderodde | I am famous (:D) | |
| Jul 25, 2015 at 5:35 | vote | accept | coderodde | ||
| Jul 25, 2015 at 1:06 | history | edited | maaartinus | CC BY-SA 3.0 |
added 3343 characters in body
|
| Jul 25, 2015 at 0:47 | history | answered | maaartinus | CC BY-SA 3.0 |