How can I count the swaps in a Merge Sort Algorithm in Python

Question

I've done the MergeSort algorithm, but I don't know how to count the swaps.

My code is:

def mergesortInv(list):
    if len(list) < 2:
        return list
    else:
        middle = len(list) // 2
        left = mergesortInv(list[:middle])   #definim les dues meitats
        right = mergesortInv(list[middle:])
        swaps=???       
    return mergeInv(left, right,swaps)

def mergeInv(left, right,swaps):
    if len(left) < 1:
        return right
    if len(right) < 1:
        return left
    if left[0] <= right[0]:
        return [left[0]] + mergeInv(left[1:],right,swaps)
    else:
        return [right[0]] + mergeInv(left,right[1:],swaps)

The output of this algorithm would be the sorted list(the algorithm works in this part) and the number of swaps: mergesortInv(list) == ([1, 2, 3, 4, 5, 7, 8], 6) 6 is the number of swaps.

swapping happens inside the `else` part of the `mergeInv` method. If you increment an index every time you come there, that should represent total swaps at the end. But you'll probably have to change your suggested function signatures. Either keep a global index (bad) or return the number of swaps in each `mergeInv`call and accumulate them (good). — Anubis, Dec 31 '17 at 10:32
Please see [Counting inversions in an array](https://stackoverflow.com/questions/337664/counting-inversions-in-an-array). The answers there show how to count inversions using mergesort, but there are other ways to do this. Please see my answer that compares the speeds of the various algorithms on different list sizes. — PM 2Ring, Dec 31 '17 at 10:37
BTW, it's not a good idea to use `list` as a variable name because that shadows the built-in `list` type. It won't hurt anything here, but it makes it a bit confusing to read your code. And if for some reason you tried to use `list` inside `mergesortInv` to create a list you'd get a mysterious error message. — PM 2Ring, Dec 31 '17 at 11:19
I've used `list` because it's a neutral name, but in my original algorithm I have got another name. — , Dec 31 '17 at 11:32

Paul Panzer · Accepted Answer · 2017-12-31T11:15:05.350

Here is a slightly modified version of your code that appears to work:

def mergesortInv(list, mergeInv):
    if len(list) < 2:
        return list, 0
    else:
        middle = len(list) // 2
        left, lc = mergesortInv(list[:middle], mergeInv)   #definim les dues meitats
        right, rc = mergesortInv(list[middle:], mergeInv)
    merge, mc = mergeInv(left, right)
    return merge, lc + rc + mc

def mergeInvRec(left, right):
    if len(left) < 1:
        return right, 0
    if len(right) < 1:
        return left, 0
    if left[0] <= right[0]:
        res, cnt = mergeInvRec(left[1:], right)
        return [left[0]] + res, cnt
    else:
        res, cnt = mergeInvRec(left, right[1:])
        return [right[0]] + res, len(left) + cnt

def mergeInvFlat(left, right):
    res, cnt = [], 0
    il, ir = 0, 0
    nl, nr = len(left), len(right)
    while il < nl and ir < nr:
        if left[il] <= right[ir]:
            res.append(left[il])
            il += 1
        else:
            res.append(right[ir])
            ir += 1
            cnt += nl - il
    res.extend(left[il:])
    res.extend(right[ir:])
    return res, cnt

It's mostly a matter of book keeping. Count the number of swaps at each step and add them. In the very last branch the first element of right bubbles all the way past every element of left which is why we tally len(left) swaps there.

Edit: As @PM2Ring points out the recursion in mergeInv is a bit reckless and will exceed Python's maximum recursion depth for moderately sized lists. I've added a non-recursive version. You can switch between the recursive and nonrecursive versions by passing their name as the second arg to the main function.

@ZRTSTR Note that this code will fail with `RecursionError: maximum recursion depth exceeded in comparison` on lists with around 1000 or more items. — PM 2Ring, Dec 31 '17 at 10:54
Much better! And quite a bit faster too. When the list size is over 40 or so it's now faster than most of the other mergesort-based versions in my timeit tests. — PM 2Ring, Dec 31 '17 at 11:29
@PM2Ring Just had a look at your linked answer. Impressed. You do seem interested in the topic ;-] — Paul Panzer, Dec 31 '17 at 11:40
I get a bit carried away sometimes... :) I quite like doing timeit tests, especially when there are a bunch of fairly different algorithms to compare. — PM 2Ring, Dec 31 '17 at 11:58

Anubis · Answer 2 · 2017-12-31T10:54:38.527

1

I didn't test this, but this is just to give you an idea about what I suggested in the comment to your question.

def mergesortInv(list):
    if len(list) < 2:
        return list
    else:
        middle = len(list) // 2
        left = mergesortInv(list[:middle])   #definim les dues meitats
        right = mergesortInv(list[middle:])
        # swaps=???
    return mergeInv(left, right)

def mergeInv(left, right):
    """ return a tuple of total swaps and the merged list """
    if len(left) < 1:
        return (0, right)
    if len(right) < 1:
        return (0, left)
    if left[0] <= right[0]:
        swaps, lst = mergeInv(left[1:],right)
        return (swaps, [left[0]] + [lst])
    else:
        swaps, lst = mergeInv(left,right[1:])
        return (swaps + 1, [right[0]] + [lst])

Usage,

swaps, lst = mergesortInv(mylist)

edited Dec 31 '17 at 10:54

answered Dec 31 '17 at 10:44

Anubis

6,995
14
56
87

This doesn't work. `mergeInv` returns a tuple, and thus so does `mergesortInv`, but inside `mergesortInv` you have `left = mergesortInv(list[:middle])` and `right = mergesortInv(list[middle:])` so both `left` and `right` get tuples assigned to them. Also, in `mergeInv`, you create nested lists with `[left[0]] + [lst]` and `[right[0]] + [lst]`. – PM 2Ring Dec 31 '17 at 11:15
BTW, a tuple is constructed by the commas, not the parentheses, the parentheses are only needed in some situations to prevent ambiguity. So you can do, eg `return 0, right`. – PM 2Ring Dec 31 '17 at 11:16

How can I count the swaps in a Merge Sort Algorithm in Python

2 Answers2