4 ms·

Just that it takes extra space and that's sometimes a constraint.

• chii 9y ago
  https://stackoverflow.com/questions/2571049/how-to-sort-in-place-using-the-merge-sort-algorithm https://stackoverflow.com/questions/2571049/how-to-sort-in-p... In place merge sort exists. It's hard to write tho
  • tomlx 9y ago
    This is beautiful. I will try to implement this once i'm at home ...
  • partycoder 9y ago
    Which decreases the space complexity but increases the time complexity.
    • stjepang 9y ago
      No, the time complexity is the same: O(n log n). The author of the top answer links to his book, where you can find a proof of time complexity: https://sites.google.com/site/algoxy/home/elementary-algorithms.pdf https://sites.google.com/site/algoxy/home/elementary-algorit...
      • EvgeniyZh 9y ago
        ...but it increases run time. It's fine not to care on hidden constants while analyzing algorithms, but not while using them in real life