|
51
|
1 from concurrent.futures import ProcessPoolExecutor
|
|
|
2 import random
|
|
|
3 from typing import List
|
|
|
4
|
|
|
5 def merge_sort(lst: List[int]) -> List[int]: # no executor parameter!
|
|
|
6 if len(lst) <= 1:
|
|
|
7 return lst
|
|
|
8 middle = len(lst) // 2
|
|
|
9 # These run in separate processes → no shared thread pool problem
|
|
|
10 left = merge_sort(lst[:middle])
|
|
|
11 right = merge_sort(lst[middle:])
|
|
|
12 return merge(left, right)
|
|
|
13
|
|
|
14 def merge(left: List[int], right: List[int]) -> List[int]:
|
|
|
15 res = []
|
|
|
16 i = j = 0
|
|
|
17 while i < len(left) and j < len(right):
|
|
|
18 if left[i] <= right[j]:
|
|
|
19 res.append(left[i])
|
|
|
20 i += 1
|
|
|
21 else:
|
|
|
22 res.append(right[j])
|
|
|
23 j += 1
|
|
|
24 res.extend(left[i:])
|
|
|
25 res.extend(right[j:])
|
|
|
26 return res
|
|
|
27
|
|
|
28 RANGE = 10_000
|
|
|
29 cpu_num = 10
|
|
|
30 def main():
|
|
|
31 data = [random.randint(0, 100) for _ in range(RANGE)]
|
|
|
32 sorted_data = []
|
|
|
33 ranges = [i for i in range(RANGE // cpu_num, RANGE, RANGE // 100)]
|
|
|
34 with ProcessPoolExecutor() as executor:
|
|
|
35 for pos_range in ranges:
|
|
|
36 sorted_data.append(executor.submit(merge_sort, data[:pos_range]).result())
|
|
|
37
|
|
|
38 while len(sorted_data) > 1:
|
|
|
39 new_sorted_data = []
|
|
|
40 for i in range(0, len(sorted_data), 2):
|
|
|
41 if
|
|
|
42 res = merge(sorted_data[i], sorted_data[i+1])
|
|
|
43 new_sorted_data.append(res)
|
|
|
44
|
|
|
45 print(len(sorted_data))
|
|
|
46
|
|
|
47 if __name__ == "__main__": # important on Windows/macOS
|
|
|
48 main()
|
