# 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:

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.

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.

Subscribe to the Statistics Globe Newsletter