Sorting unsorted and partially sorted lists using the natural merge sort
James Harris · Software Practice and Experience · 1981
Abstract A version of the natural merge sort is shown to be an efficient method for both nearly sorted data and for random data. This method is compared with quickersort, 2‐way merge sort, and Cook and Kim's method for various sortedness ratios.