Natural Merge Sort in Python (Example)

Natural merge sort is a variation of merge sort that aims to exploit existing order in the input data to improve efficiency. Whether natural merge sort is more efficient than normal Recursive Merge Sort depends on the characteristics of the input data. It aims to minimize the number of comparisons required during the sorting process. In this tutorial, we will walk through the steps of implementing natural merge sort in the Python programming language.

The tutorial will consist of these topics:

Let’s start right away…

Creating Example Data

The following data will be used as a basis for this tutorial:

my_list = [-1, -5, -40, 100, 589, 27, -95]    # initializing example list

As you can see based on the previous output of the Python console, our exemplifying data is an integer list.

Example: Implementing Natural Merge Sort

First, let’s implement a merge function that takes two sorted lists and merges them into a single sorted list. The function compares the left and right sublists and appends the lower element to the merged list. Once one of the lists has no further elements to check, the remaining elements are appended to the merged list. This function will be used in the later steps of natural merge sort. Also, in this implementation, we utilize the extend() function which provides a more concise implementation of adding the remaining elements of the left and right sublists.

def merge_runs(left, right):                  # function for merging the runs
    merged = []
    i = 0
    j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])                   # appending rest of 'left' to the 'merged' list
    merged.extend(right[j:])                  # appending rest of 'right' to the 'merged' list
    return merged

Now, let’s implement the natural merge sort function that divides the input list into runs recursively and merges them until the list is completely sorted. We will define a function called natural_merge_sort() to run the natural merge sort algorithm.

The function first checks if the list has one or less elements. If it does, it simply returns the list. Otherwise, using a simple loop, it finds the runs in the list. A run is a subsequence where the elements are in increasing or decreasing order.

def natural_merge_sort(my_list):
    if len(my_list) <= 1:                     # checking if the my_list is already sorted
        return my_list
    runs = []
    start = 0
    end = 1
    while end < len(my_list):                 # finding the runs in the my_list
        if my_list[end] < my_list[end-1]:
            runs.append(my_list[start:end])
            start = end
        end += 1
    runs.append(my_list[start:end])

Once the runs have been found, the function repeatedly merges adjacent runs until only one run remains. The merging is done using the merge_runs() function, which merges two sorted arrays into one sorted array.

    while len(runs) > 1:                      # merging the runs
        merged_runs = []
        i = 0
        while i < len(runs)-1:
            merged_runs.append(merge_runs(runs[i], runs[i+1]))
            i += 2
        if len(runs) % 2 == 1:
            merged_runs.append(runs[-1])
        runs = merged_runs
    return runs[0]

Finally, once we call the natural_merge_sort() function, we can see that it takes an unsorted list as input and returns a sorted list.

print(natural_merge_sort(my_list))
# [-95, -40, -5, -1, 27, 100, 589]

Here is the full code for your convenience:

my_list = [-1, -5, -40, 100, 589, 27, -95]    # initializing example list
 
def merge_runs(left, right):                  # function for merging the runs
    merged = []
    i = 0
    j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])                   # appending rest of 'left' to the 'merged' list
    merged.extend(right[j:])                  # appending rest of 'right' to the 'merged' list
    return merged
 
def natural_merge_sort(my_list):
    if len(my_list) <= 1:                     # checking if the my_list is already sorted
        return my_list
    runs = []
    start = 0
    end = 1
    while end < len(my_list):                 # finding the runs in the my_list
        if my_list[end] < my_list[end-1]:
            runs.append(my_list[start:end])
            start = end
        end += 1
    runs.append(my_list[start:end])
    while len(runs) > 1:                      # merging the runs
        merged_runs = []
        i = 0
        while i < len(runs)-1:
            merged_runs.append(merge_runs(runs[i], runs[i+1]))
            i += 2
        if len(runs) % 2 == 1:
            merged_runs.append(runs[-1])
        runs = merged_runs
    return runs[0]
 
print(natural_merge_sort(my_list))
# [-95, -40, -5, -1, 27, 100, 589]

In the end, natural merge sort is an efficient sorting algorithm that takes advantage of existing order in the input data. By dividing the list into runs and merging them, it reduces the number of comparisons required, resulting in faster sorting. You can now use this implementation to sort arrays or lists in your Python projects.

If you want a visual explanation of how merge sort algorithms work, feel free to check out the Visualization of Merge Sort tutorial as well.

Video & Further Resources

Do you need further explanations on the contents of this article? Then you might want to have a look at the following video on my YouTube channel. I explain the Python programming codes of this tutorial in the video:

The YouTube video will be added soon.

Furthermore, you may read the other articles on this website. I have published several articles that are related to the implementation of natural merge sort already.

• Merge Sort List in Python
• Iterative Bottom Up Merge Sort in Python
• Function & Library for Merge Sort in Python
• k-way Merge Sort in Python
• All Python Programming Examples

In this tutorial, I have explained how to sort a list with natural merge sort in Python. In case you have any further questions, please let me know in the comments section.

This page was created in collaboration with Ömer Ekiz. Have a look at Ömer’s author page to get more information about his professional background, a list of all his tutorials, as well as an overview of his other tasks on Statistics Globe.