Faster Python merge with less auxiliary space?sort
In Algorithms fourth editionAlgorithms 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?
Faster merge with less auxiliary space?
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?
Python merge sort
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?
Faster merge with less auxiliary space?
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?