k-way Merge Sort in Python (Example)

 

In this Python programming tutorial, you’ll learn how to implement a k-way merge sort algorithm.

The post is structured as follows:

Here’s the process step by step!

 

Creation of Example Data

Firstly, let’s create a sample list for the example.

the_list = [-14, 25, 31, 40, 856, 1, -100, -25, 28, 85]

Let’s now use the k-way merge sort algorithm to sort the_list!

 

Example: Implementation of k-way Merge Sort

The following Python syntax shows how to define a function that sorts a list based on the merge sort algorithm utilizing the divide-and-conquer algorithmic paradigm. The k-way merge sort algorithm is the more dynamic version of the merge sort, which has the option to modify how many sublists each list can be split into. Let’s check how below!

def k_way_merge_sort(arr, k=2):
    n = len(arr)
    if n <= 1:                                                                         # checking the array size
        return arr
    else:
        sublists = [arr[i:i+n//k] for i in range(0, n, n//k)]                          # splitting to sublists
        sorted_sublists = [k_way_merge_sort(sublist, k) for sublist in sublists]       # calling the function on the sublists
        sorted_arr = []
        while any(sorted_sublists):                                                    # checking if there are any sublists to sort
            lowest = min([lst[0] for lst in sorted_sublists if lst], key=lambda x: x)  # finding lowest element in sublists
            for i in range(len(sorted_sublists)):                                      # finding where the lowest element if and removing it
                if sorted_sublists[i] and sorted_sublists[i][0] == lowest:
                    sorted_sublists[i] = sorted_sublists[i][1:]
                    break
            sorted_arr.append(lowest)                                                  # adding the lowest element to the sorted list
        return sorted_arr 
 
print(k_way_merge_sort(the_list))
# [-100, -25, -14, 1, 25, 28, 31, 40, 85, 856]

This implementation takes an input list arr and an optional parameter k that specifies how many sublists that arr will be split into. The default value 2 is assigned to k, which makes the computation correspond to the generic merge-sort algorithm.

We first check if the length of arr is less than or equal to 1; in this case, we can simply return arr itself since it has only one element or is empty, hence there is nothing to sort. Otherwise, we split arr into k sublists using list comprehension, [k_way_merge_sort(sublist, k) for sublist in sublists], and recursively call k_way_merge_sort() on each sublist to sort them.

Then we create an empty list sorted_arr to hold the sorted values. We repeatedly find the lowest value among the first elements of all non-empty sublists, remove that value from its sublist, and append it to sorted_arr. We continue doing this until all sublists are empty, at which point sorted_arr contains the fully-sorted list.

This is the end of our k-way Merge Sort tutorial. I hope you find it helpful!

 

Video, Further Resources & Summary

Would you like to learn more about the implementation of the k-way merge sort? Then I can recommend having a look at the following video on my YouTube channel. In the video, I show the Python code of this tutorial:

 

The YouTube video will be added soon.

 

In addition, you may want to read the other tutorials which I have published on my website.

 

In this tutorial, you have learned how to sort a list via k-way merge sort in Python. If you have further questions, please tell me about it in the comments section below.

 

Ömer Ekiz Python Programming & Informatics

This page was created in collaboration with Ömer Ekiz. 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

Get regular updates on the latest tutorials, offers & news at Statistics Globe.
I hate spam & you may opt out anytime: Privacy Policy.


Leave a Reply

Your email address will not be published. Required fields are marked *

Fill out this field
Fill out this field
Please enter a valid email address.

Top