NaturalMergeSort

index.html visualises how Natural Merge Sort works in general

algorithm.js is a possible Javascript implementation

Basic idea

Initially sorted elements do not need to be sorted again. In the worst case, Natural Merge Sort has the same speed as Merge Sort.

To simplify understanding, this implementation uses recursion and does not take advantage of all possible optimisations.