Python merge sort

Question

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?

Answer 1

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:

• use of whitespaces in the expressions and statements

• Lerner Zhang: Yes, you are right. deepcopy(precisely shallow copy) is not necessary here.

Answer 2

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]