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

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.

Top