Merge Sort in Ascending & Descending Order in Python (Example)

This tutorial illustrates how to implement a merge sort algorithm with sort order option in the Python programming language.

Table of contents:

So without further additions, let’s dive into it.

Creation of Example Data

In the first place, let’s create some example data:

sample_lst = [4, 2, 1, 5, 3]                      # sample list generation

Now that our data is ready. Let’s check out the implementation!

Example: Implementation of Merge Sort with Order Option

This example illustrates how to add an optional parameter to the standard merge sort algorithm for lists. The list goes through a size check to verify whether it is large enough to be split into two sublists; if not, the list is returned without any further operations.

If the list has two or more elements, then the list is divided into two halves: left_half and right_half. Then the merge_sort() function is recursively called for the sublists. This means a separate merge_sort() execution is started for the sublists where first their length will be checked, then if they have enough elements, they will be split into two sublists themselves and new merge_sort() executions will be generated on their sublists.

For any of the recursive calls, once their sublist merge_sort() executions terminate and the sublists are sorted, the merge() function is called for combining the two halves. Until here, the algorithm works like the standard merge sort, but we will observe some slight additions in the merge() function.

Let’s have a look!

def merge_sort(lst, reverse=False):
    if len(lst) <= 1:                             # checking if the dictionary needs sorting
        return lst
 
    mid = len(lst) // 2
    left_half = lst[:mid]                         # constructing left_half sublist
    right_half = lst[mid:]                        # constructing right_half sublist
 
    left_half = merge_sort(left_half, reverse)    # calling the function recursively on left_half
    right_half = merge_sort(right_half, reverse)  # calling the function recursively on right_half
 
    return merge(left_half, right_half, reverse)

In the merge() function, the sort order option is added via a third parameter: reverse. If the reverse is set to True, then the elements are ordered in decreasing order and vice versa.

In the body of the function, an empty list result is created. Then the elements pointed out by the indices i and j are compared, and one of them is chosen to be inserted into result.

When there are no elements left in one sublist, the remaining elements are inserted directly into the final list result via extend().

def merge(left_half, right_half, reverse):
    result = []
    i = j = 0
    while i < len(left_half) and j < len(right_half):
        if reverse:
            if left_half[i] > right_half[j]:      # executed if the left half has the greater element
                result.append(left_half[i])
                i += 1
            else:                                 # executed if the right half has the greater element
                result.append(right_half[j])
                j += 1
        else:
            if left_half[i] < right_half[j]:      # executed if the left half has the lower element
                result.append(left_half[i])
                i += 1
            else:                                 # executed if the right half has the lower element
                result.append(right_half[j])
                j += 1
    result.extend(left_half[i:])                  # adding remaining elements of left half
    result.extend(right_half[j:])                 # adding remaining elements of right half
    return result

As you can see, reverse=True results in descending order and reverse=False leads to the output in ascending order.

ascending_sorted_lst = merge_sort(sample_lst)
descending_sorted_lst = merge_sort(sample_lst, reverse=True)
 
print(ascending_sorted_lst)
# [1, 2, 3, 4, 5]
print(descending_sorted_lst)
# [5, 4, 3, 2, 1]

Hope this tutorial helps. See you in the next tutorial!

Video, Further Resources & Summary

Do you need further explanations on the Python codes of the present post? Then I recommend watching the following video on the Statistics Globe YouTube channel. In the video, I’m explaining the examples of this post:

The YouTube video will be added soon.

Besides the video, you may want to read the related tutorials on this website. Some articles that are related to the implementation of merge sort with sort order option can be found below.

• External Merge Sort in Python
• 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 article, you have learned how to create a merge sort algorithm with a sort order option in Python. In case you have additional 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.