3 ms·

you can do merge sort in place

hinkley 7y ago
You can’t. Merge sort copies data back and forth between two spaces the size of the data set. That’s O(n) extra space. I spent some time four summers ago with merge sort. I had a PoC for an in-place algorithm that survived several rounds of poorly selected sample data. That was quite a disappointment. In looking around I believe I ran across several implementations that required sqrt(n) extra space and one that I think claimed log n but was so complicated I never did figure out why it was supposed to work. At least one of these had higher time complexity, but often enough you need to work with data sets that dominate your memory footprint. Even a second array of pointers might push you over.
- z0r 7y ago
  i couldn't find a direct reference, but i remembered that sedgewick's c++ algorithms book had an in-place iterative mergesort with no auxiliary space. that probably was a false memory, but it seems that there is such a beast: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.5514&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22....
  - hinkley 7y ago
    I remember this article now. As someone else said, for certain time complexities there are more algorithms available. I believe when I realized that fixing my bug would turn it essentially into this algorithm, I found something else to do.
    - z0r 7y ago
      I just tried to read this, and not only is it horrifyingly complex it isn't stable, so it doesn't really fit the bill (even if you allow for strange complexities)
      - hinkley 7y ago
        Aha! Thank you. That solves a mystery for me. Skimming it a few minutes ago, I thought it claimed to be stable, and I couldn't figure out why it didn't come to mind when I thought about merge sort. If it's not stable, then what's the point? It's not a merge sort variant by the most important measure, IMO, and as I said, I was only considering merge sort variants. Even with all of the additional logic people have created to avoid worst case performance, quicksort is simpler than this algorithm by a huge margin.
- anderskaseorg 7y ago
  Algorithms for stable, in-place merging in linear time, hence merge sorting in O(n log n) time, have been known since 1977 (https://doi.org/10.1137/0206025 https://doi.org/10.1137/0206025). This first algorithm was too complicated with too large of a constant factor to be practical, but has since been improved.
  - hinkley 7y ago
    How many people do you suppose can read that link?
    - kbirkeland 7y ago
      Google scholar returns a pdf[0] when searching the doi. [0] https://epubs.siam.org/doi/pdf/10.1137/0206025 https://epubs.siam.org/doi/pdf/10.1137/0206025
  - hinkley 7y ago
    It concerns me that the most recent citation in that bibliography says “ We achieve our goal using Recursive Partitioning combined with In Place merging to sort a given array” Stack frames are external storage. I’d have to see the code to see how they manage to do recursion without log(n) external storage. Traditional merge sort can be written using iteration, which makes the external storage for sort state O(1), but the semi spaces are still there.
    - cbarrick 7y ago
      To be fair, tail calls don't require stack frames. If it's just a matter of keeping up with the bounds of the partitions, I can see that being done in constant space.
      - hinkley 7y ago
        This isn’t a tail call situation, though. In order to convert it to iteration you have to use external storage.
    - 7y ago

You can’t. Merge sort copies data back and forth between two spaces the size of the data set. That’s O(n) extra space. I spent some time four summers ago with merge sort. I had a PoC for an in-place algorithm that survived several rounds of poorly selected sample data. That was quite a disappointment. In looking around I believe I ran across several implementations that required sqrt(n) extra space and one that I think claimed log n but was so complicated I never did figure out why it was supposed to work. At least one of these had higher time complexity, but often enough you need to work with data sets that dominate your memory footprint. Even a second array of pointers might push you over.

z0r 7y ago
i couldn't find a direct reference, but i remembered that sedgewick's c++ algorithms book had an in-place iterative mergesort with no auxiliary space. that probably was a false memory, but it seems that there is such a beast: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.5514&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22....
- hinkley 7y ago
  I remember this article now. As someone else said, for certain time complexities there are more algorithms available. I believe when I realized that fixing my bug would turn it essentially into this algorithm, I found something else to do.
  - z0r 7y ago
    I just tried to read this, and not only is it horrifyingly complex it isn't stable, so it doesn't really fit the bill (even if you allow for strange complexities)
    - hinkley 7y ago
      Aha! Thank you. That solves a mystery for me. Skimming it a few minutes ago, I thought it claimed to be stable, and I couldn't figure out why it didn't come to mind when I thought about merge sort. If it's not stable, then what's the point? It's not a merge sort variant by the most important measure, IMO, and as I said, I was only considering merge sort variants. Even with all of the additional logic people have created to avoid worst case performance, quicksort is simpler than this algorithm by a huge margin.
anderskaseorg 7y ago
Algorithms for stable, in-place merging in linear time, hence merge sorting in O(n log n) time, have been known since 1977 (https://doi.org/10.1137/0206025 https://doi.org/10.1137/0206025). This first algorithm was too complicated with too large of a constant factor to be practical, but has since been improved.
- hinkley 7y ago
  How many people do you suppose can read that link?
  - kbirkeland 7y ago
    Google scholar returns a pdf[0] when searching the doi. [0] https://epubs.siam.org/doi/pdf/10.1137/0206025 https://epubs.siam.org/doi/pdf/10.1137/0206025
- hinkley 7y ago
  It concerns me that the most recent citation in that bibliography says “ We achieve our goal using Recursive Partitioning combined with In Place merging to sort a given array” Stack frames are external storage. I’d have to see the code to see how they manage to do recursion without log(n) external storage. Traditional merge sort can be written using iteration, which makes the external storage for sort state O(1), but the semi spaces are still there.
  - cbarrick 7y ago
    To be fair, tail calls don't require stack frames. If it's just a matter of keeping up with the bounds of the partitions, I can see that being done in constant space.
    - hinkley 7y ago
      This isn’t a tail call situation, though. In order to convert it to iteration you have to use external storage.
  - 7y ago