StandardIO
StandardIO

Reputation: 336

Is this an acceptable implementation of non recursive merge sort

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

Answers (0)

Related Questions