﻿ Multi-threaded merge sort in Python

## Python Multi-threading: Exercise-5 with Solution

Write a Python program to implement a multi-threaded merge sort algorithm.

Sample Solution:

Python Code:

``````import threading
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
left = merge_sort(left)
right = merge_sort(right)
return merge(left, right)
def merge(left, right):
merged = []
i = j = 0

while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1

while i < len(left):
merged.append(left[i])
i += 1

while j < len(right):
merged.append(right[j])
j += 1
return merged
return merge_sort(arr)
# Divide the input list into equal-sized sublists
sublists = [arr[i:i+size] for i in range(0, len(arr), size)]
# Create threads for sorting each sublist
sorted_sublists = []
for sublist in sublists:
# Wait for all threads to complete
# Merge the sorted sublists
merged = sorted_sublists[0]
for sublist in sorted_sublists[1:]:
merged = merge(merged, sublist)
return merged
# Example usage
input_list = [ 4,5,8,3,0,5,3,9,4,3]
print("Original List:", input_list )
print("Sorted list:", sorted_list)
``````

Sample Output:

```Original List: [4, 5, 8, 3, 0, 5, 3, 9, 4, 3]
Sorted list: [0, 3, 3, 3, 4, 4, 5, 5, 8, 9]
```

Explanation:

In the above exercise, we define a "merge_sort()" function that implements the regular merge sort algorithm to sort a given list. A "merge()" function is also defined, which merges two sorted lists into one.

The "multi_threaded_merge_sort()" function takes the input list and the number of threads as arguments. It divides the input list into equal-sized sublists and creates threads for sorting each sublist. Each thread runs the "merge_sort()" function independently. After all the threads complete, the program merges the sorted sublists using the "merge()" function.

Flowchart:

Have another way to solve this solution? Contribute your code (and comments) through Disqus.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.

﻿