Mergesort problem

Chris Angelico rosuav at gmail.com
Wed Dec 21 20:46:02 EST 2016


On Thu, Dec 22, 2016 at 11:55 AM, Deborah Swanson
<python at deborahswanson.net> wrote:
> The problem is that while mergeSort puts the list ls in perfect order,
> which I can see by looking at result on merge's final return to
> mergeSort, and at the left and the right once back in mergeSort. Both
> the left half and the right half are in order. But the list L is still
> in its original order, and after mergeSort completes, ls is still in its
> original order. Maybe there's some bonehead error causing this, but I
> just can't see it.
>

Your analysis is excellent. Here's what happens: When you merge-sort,
you're always returning a new list (either "return L[:]" or "result =
[]"), but then you call it like this:

    # sort: Description only, to make hyperelinks & find duplicates
    mergeSort(ls)

This calls mergeSort, then drops the newly-sorted list on the floor.
Instead, try: "ls = mergeSort(ls)".

Thank you for making it so easy for us!

ChrisA


More information about the Python-list mailing list