Reputation: 336
I'm learning to code, I just read the chapter divide and conquer in the introduction to algorithms book. But I don't like the recursive algorithms and is very hard to my undertand it for that reason I tried to make a non recursive merge sort in Python.
Can this implementation be considered a correct non recursive merge sort algorithm?
import numpy as np
A = np.random.randn(10) # Unordered array, can be a list too
print(A)
# Creating the first indexes groups
# All the indixes start in individual groups,
# so the algorithm start merging in the first iteration.
# [[1],[2],...,[n]] # first iteration index grouping
# [[1,2],[3,4],...[n-1, n] or [[1,2],[3,4],...[n]] # second iteration
# [[1,2,3,4],[4,5,6,7]....[n-3, n-2, n-1, n] or ... # third iteration ...
idx_group = [[i] for i in range(len(A))]
# Stop when only exist a only group.
while len(idx_group)>1:
new_idxGroup = []
mid = len(idx_group)
for i in range(0 ,mid ,2):
if i+1 < mid:
# Copying values for left and right tree childs to marge
# bottom up
left_values = [A[j] for j in idx_group[i]] + [np.inf]
right_values = [A[j] for j in idx_group[i+1]] + [np.inf]
start_idx = idx_group[i][0]
end_idx = idx_group[i+1][-1]
# Merge part
ii = 0
jj = 0
# iterate over over all range of values to merge
# in the original array (A)
for j in range(start_idx, end_idx+1):
if left_values[ii]<right_values[jj]:
A[j] = left_values[ii]
ii += 1
else:
A[j] = right_values[jj]
jj += 1
# index grouping
new_idxGroup.append(idx_group[i]+idx_group[i+1])
else:
# not pair group, just pass to the next iteration
new_idxGroup.append(idx_group[i])
idx_group = new_idxGroup
print('Ordered array', A)
Exit:
Unordered array: [ 0.43556583 -0.1282962 1.46197799 0.2420687 0.57725809 -1.47126681
-1.05106971 -0.456238 0.22736302 -1.30470431]
Ordered array [-1.47126681 -1.30470431 -1.05106971 -0.456238 -0.1282962 0.22736302
0.2420687 0.43556583 0.57725809 1.46197799]
Upvotes: 1
Views: 72