Merge Sort count comparisons
<p>The questions are: 1) Is that correct code to count comparisons?
2) How can I return counter with sorted list like ([1,2,3,4], number_of_comparisons) Code:</p>

<pre><code>counter = 0
def merge_sort(lst):
"""Sorts the input list using the merge sort algorithm.

&gt;&gt;&gt; lst = [4, 5, 1, 6, 3]
&gt;&gt;&gt; merge_sort(lst)
[1, 3, 4, 5, 6]
"""
if len(lst) &lt;= 1:
    return lst
mid = len(lst) // 2
left = merge_sort(lst[:mid])
right = merge_sort(lst[mid:])
return merge(left, right), counter

def merge(left, right):
"""Takes two sorted lists and returns a single sorted list by comparing the elements one at a time.

&gt;&gt;&gt; left = [1, 5, 6]
&gt;&gt;&gt; right = [2, 3, 4]
&gt;&gt;&gt; merge(left, right)
[1, 2, 3, 4, 5, 6]
"""
global counter
if not left:
    return right
if not right:
    return left
counter += 1
if left[0] &lt; right[0]:
    return [left[0]] + merge(left[1:], right)
return [right[0]] + merge(left, right[1:])


lst = [4, 5, 1, 6, 3]
print(merge_sort(lst))
</code></pre>

<p>Output: </p>

<pre><code>([1,3,4,5,6], counter)
</code></pre>

<p>The answer is yes, this code may count the number of comparisons, 
but you have to clearly understand what do you want to count</p>

<p>Here are some modifications, you may remove them if you don't need them</p>

<pre><code>counter = 0


def merge_sort(lst):
    global counter
    if len(lst) &lt;= 1:
        counter += 1 # increment counter when we dividing array on two
        return lst
    mid = len(lst) // 2
    left = merge_sort(lst[:mid])
    right = merge_sort(lst[mid:])
    return merge(left, right)


def merge(left, right):
    global counter
    if not left:
        counter += 1 # increment counter when not left (not left - is also comparison)
        return right
    if not right:
        counter += 1 # the same as above for right
        return left
    if left[0] &lt; right[0]:
        counter += 1 # and the final one increment
        return [left[0]] + merge(left[1:], right)
    return [right[0]] + merge(left, right[1:])


lst = [4, 5, 1, 6, 3]
# also you don't need to return counter since you are using global value
print(merge_sort(lst), counter)
</code></pre>

<p><a href="http://codereview.stackexchange.com/questions/12922/inversion-count-using-merge-sort">Also you may try to look here!</a></p>

python