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.