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>I've found a solution in that way:</p>

<pre><code>def merge_sort(input_array):
counter = 0

if len(input_array) &lt;= 1:
    return input_array, counter

left_part = merge_sort(input_array[:len(input_array) // 2])
right_part = merge_sort(input_array[len(left_part[0]):])

counter += left_part[1] + right_part[1]

left_ndx = 0
right_ndx = 0
final_ndx = 0

while left_ndx &lt; len(left_part[0]) and right_ndx &lt; len(right_part[0]):
    counter += 1
    if left_part[0][left_ndx] &lt; right_part[0][right_ndx]:
        input_array[final_ndx] = left_part[0][left_ndx]
        left_ndx += 1
    else:
        input_array[final_ndx] = right_part[0][right_ndx]
        right_ndx += 1
    final_ndx += 1

while left_ndx &lt; len(left_part[0]):
    input_array[final_ndx] = left_part[0][left_ndx]
    left_ndx += 1
    final_ndx += 1
    counter += 1

while right_ndx &lt; len(right_part[0]):
    input_array[final_ndx] = right_part[0][right_ndx]
    right_ndx += 1
    final_ndx += 1
    counter += 1

return input_array, counter
</code></pre>

<p>So the output would be:</p>

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

python