InAlgorithms 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: breakHave I implemented it as required? Or can it be improved further?
2 Answers2
I don't think you needdeque() 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:
- \$\begingroup\$Yes, you are right. deepcopy(precisely shallow copy) is not necessary here.\$\endgroup\$Lerner Zhang– Lerner Zhang2018-12-16 12:58:05 +00:00CommentedDec 16, 2018 at 12:58
Disclaimer: I haven't tried to run your code nor the modifications I wrote.
Being explicit
Instead of using[::-1], I'd recommend usingreversed which is easier to read but more verbose.
Also, as you are already usingif/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]
You mustlog in to answer this question.
Explore related questions
See similar questions with these tags.