1
$\begingroup$

I ran into natural mergesort in this Wikipedia page: https://en.wikipedia.org/wiki/Merge_sort#Natural_merge_sort

However, I can't find much information regarding:

  1. The algorithm(s) to achieve natural mergesort, and the pros and cons of each method
  2. How natural mergesort compares to bottom-up mergesort (pros and cons of each w.r.t the other)

In short, I'm looking for resources that would teach me algorithms to do natural mergesort, and how to weigh it against the usual bottom-up mergesort

$\endgroup$
1
$\begingroup$

Natural Mergesort usually refers to Timsort. In terms of comparison to bottom-up mergesort, Timsort has $O(n)$ best-case running time where as bottom-up mergesort is at least $O(n\log n)$ on any input.

However, analysis of the worst-case running time of Timsort proves to be more tricky; an 2018 paper [1] establishes that its worst-case time complexity is $O(n\log \rho)$, where $\rho$ is the number of maximal monotonic sequences in the input array.

[1]: Nicolas Auger, Vincent Jugé, Cyril Nicaud, Carine Pivoteau, "On the Worst-Case Complexity of TimSort"

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.