In Algorithms Fourth Edition by Robert Sedgewick and Kevin Wayne, the exercise 2.2.10 states that:
Implement a version of merge() that copies the second half of a to aux in decreasing order and then does the merge back to a. This change al- lows you to remove the code to test that each of the halves has been exhausted from the inner loop.
This is my code in Python:
def merge(a, lo, mi, hi): aux_hi = deque(a[mi:hi]) for i in range(lo, hi)[::-1]： if aux_hi: last_a = i-len(aux_hi) if last_a < lo: a[i] = aux_hi.pop() else: a[i] = aux_hi.pop() if aux_hi[-1] > a[last_a] else a[last_a] else: break
Have I implemented it as required? Or can it be improved further?