Mercurial

comparison async_multi_threads/merge_sort.py @ 69:551d9fc0a2ba

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Updated wrong names.
author June Park <parkjune1995@gmail.com>
date Thu, 25 Dec 2025 20:07:46 -0800
parents
children
comparison
equal deleted inserted replaced
68:70ca1d99f3fd 69:551d9fc0a2ba
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()