2
\$\begingroup\$

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?

\$\endgroup\$
1
\$\begingroup\$

I don't think you need deque() as you are popping from the end / right side which is a \$O(1)\$ operation for regular lists:

aux_hi = a[mi:hi]

There are some minor concerns regarding:

\$\endgroup\$
  • \$\begingroup\$ Yes, you are right. deepcopy(precisely shallow copy) is not necessary here. \$\endgroup\$ – Lerner Zhang Dec 16 '18 at 12:58
1
\$\begingroup\$

Disclaimer: I haven't tried to run your code nor the modifications I wrote.

Being explicit

Instead of using [::-1], I'd recommend using reversed which is easier to read but more verbose.

Also, as you are already using if/else you could get rid of the ternary operator to write the more explicit:

        if last_a < lo:
            a[i] = aux_hi.pop()
        elif aux_hi[-1] > a[last_a]:
            a[i] = aux_hi.pop()
        else:
            a[i] = a[last_a]

which can be re-organised as:

        if (last_a < lo or aux_hi[-1] > a[last_a]):
            a[i] = aux_hi.pop()
        else:
            a[i] = a[last_a]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.