Implementation
1def merge_sort_bottom_up(arr):
2 if arr is None or len(arr) == 0:
3 raise ValueError("Array is empty")
4 if len(arr) <= 1:
5 return arr
6
7 n = len(arr)
8 group_size = 1
9
10 # Keep iterating while group_size is less than the length of the array
11 while group_size < n:
12 for i in range(0, n, 2 * group_size):
13 left_start = i
14 left_end = min(i + group_size, n)
15 right_start = left_end
16 right_end = min(i + 2 * group_size, n)
17
18 left = arr[left_start:left_end]
19 right = arr[right_start:right_end]
20
21 l, r, arr_pos = 0, 0, left_start
22
23 # Merge two sorted subarrays (sorted because of previous passes and we start with size 1)
24 while l < len(left) and r < len(right):
25 if left[l] < right[r]:
26 arr[arr_pos] = left[l]
27 l += 1
28 else:
29 arr[arr_pos] = right[r]
30 r += 1
31 arr_pos += 1
32
33 # If left subarray is not exhausted
34 while l < len(left):
35 arr[arr_pos] = left[l]
36 l += 1
37 arr_pos += 1
38
39 # If right subarray is not exhausted
40 while r < len(right):
41 arr[arr_pos] = right[r]
42 r += 1
43 arr_pos += 1
44
45 # Double the group size after each pass
46 group_size *= 2
47
48 return arr
49