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

- Sort List of datetime Objects in Python
- Visualization of Merge Sort in Python
- Python Programming Language
- Pseudocode for Merge Sort in Python
- Function & Library for Merge Sort in Python

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.