I wrote a merge sort function and thought I was done.. but in the assignment it says that the function is supposed to sort the actual list instead of creating a copy (so call by value instead of reference I think?). Right now, it doesn't work because the list itself isn't changed.
def mergeSort(L, ascending = True):
print('Mergesort, Parameter L:')
print(L)
result = []
if len(L) == 1:
return L
mid = len(L) // 2
teilliste1 = mergeSort(L[:mid], ascending)
teilliste2 = mergeSort(L[mid:], ascending)
x, y = 0, 0
while x < len(teilliste1) and y < len(teilliste2):
if (ascending and teilliste1[x] > teilliste2[y]) or (not ascending and teilliste1[x] < teilliste2[y]):
result.append(teilliste2[y])
y = y + 1
else:
result.append(teilliste1[x])
x = x + 1
result = result + teilliste1[x:]
result = result + teilliste2[y:]
return result
liste1 = list([3, 2, -1, 9, 17, 4, 1, 0])
mergeSort(liste1)
print(liste1) # result will be the unsorted list
What do I need to change in the function to make it call by value and sort the actual list?
I know I could do
mergeResult = mergeSort(liste1)
print(mergeResult)
but apparently I have to change the original parameter list.
There are two basic ways to write a recursive decomposition function. The immutable version calls itself on copies of two smaller parts, then reassembles and returns them; that's what you wrote. The mutable version calls itself on the actual input, then modifies that in-place, and returns nothing; that's what your teacher wants here.
Notice that, unlike some other sorting algorithms, mergesort can't be done with constant extra storage, only better than linear extra storage. (Logarithmic is possible, but complicated; I doubt your teacher is insisting on that.) And because of this, most mergesort algorithms you find in books, Wikipedia, etc. will be written as copying sorts rather than in-place sorts. Which means this is probably a bit of a "trick question", trying to see whether you can figure out how to convert from the well-known copying version of the algorithm into an in-place version with explicit extra storage.
You can always write an immutable algorithm and then mutate at the very end, e.g.:
def _mergesort(L, ascending):
# your existing code
def mergesort(L, ascending=True):
L[:] = _mergesort(L, ascending)
This gives you all the cost of immutability without the benefits. But it does mean you can write a variety of sort functions with the same API, which are all implemented in-place if that's a reasonable optimization, but not if it isn't, which seems to be what your teacher is after.
If you don't want a wrapper function, you can change the last line from:
return result
… to:
L[:] = result
However, because this changes the API, you also need to change your recursive calls to match. For example, you could do this:
teilliste1 = L[:mid]
mergeSort(teilliste1, ascending)
teilliste2 = L[mid:]
mergeSort(teilliste2, ascending)
In Python, a mutating recursive decomposition function often works by passing start and end indices down with the list, like this:
def mergesort(L, ascending=True, start=None, stop=None):
if start is None: start = 0
if stop is None: stop = len(L)
if stop - start <= 1:
return
mid = (stop - start) // 2 + start
mergeSort(L[start:mid], ascending)
mergeSort(L[mid:stop], ascending)
# etc.
As mentioned above, the merging step is going to require some auxiliary storage. The simplest thing to do—and probably good enough for your assignment, even though it means linear space—is to just build up a left list and a right list and then assign them back into L[start:mid], L[mid:stop] = left, right.
Notice that this isn't all that different from the L[:] = result version above; it's really just a matter of using L itself, together with start and stop indices, in place of copies for the first half of the process, and then copying only at the end during the merge.