Timeline for Merge sort implementation using iterators
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 11, 2017 at 5:19 | vote | accept | Abhinav Gauniyal | ||
| Feb 10, 2017 at 20:55 | comment | added | ratchet freak | @coderodde the tricky part is at the recursion stop to decide whether to swap in place on length == 2 or do a merge to the other buffer. Which requires passing down a flag to know where the result should end up (into src or dst). | |
| Feb 10, 2017 at 20:49 | comment | added | coderodde | Never done that before. Yet I have to disagree with that is tricky to do in the recursive version. After all, in your top recursive call there is only two cases to try what comes to the initial source/target array arrangement. | |
| Feb 10, 2017 at 20:18 | comment | added | ratchet freak | @coderodde you can adjust for that by letting the last range be larger by doing a extra merge if the last block size < 0.5*the current block size | |
| Feb 10, 2017 at 17:59 | comment | added | coderodde | The bottom-up mergesort suffers from the following: suppose the length of the input range is \$2^k + 1\$, where \$k\$ is a positive integer. Now the very last merge will merge a run of length \$2^k\$ with a run of length of one element. (One single element will introduce an entire pass over the range.) | |
| Feb 10, 2017 at 17:40 | comment | added | Incomputable | @AbhinavGauniyal, I think that if move isn't possible it will still compile. But if move can throw, the story changes a lot. | |
| Feb 10, 2017 at 16:57 | comment | added | Incomputable | Point of OP is correct, there should be some fallback mechanism. Solution can be std::move_if_noexcept() | |
| Feb 10, 2017 at 16:01 | comment | added | Abhinav Gauniyal | if move isn't possible, will that operation fail to compile or switch to copy operation? | |
| Feb 10, 2017 at 14:25 | history | answered | ratchet freak | CC BY-SA 3.0 |