Sorting unsorted and partially sorted lists using the natural merge sort

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.