问题描述:

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:

`counter = 0`

def merge_sort(lst):

"""Sorts the input list using the merge sort algorithm.

>>> lst = [4, 5, 1, 6, 3]

>>> merge_sort(lst)

[1, 3, 4, 5, 6]

"""

if len(lst) <= 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.

>>> left = [1, 5, 6]

>>> right = [2, 3, 4]

>>> 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] < 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))

Output:

`([1,3,4,5,6], counter)`

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

Here are some modifications, you may remove them if you don't need them

```
counter = 0
def merge_sort(lst):
global counter
if len(lst) <= 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] < 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)
```

Also you may try to look here!

I've found a solution in that way:

```
def merge_sort(input_array):
counter = 0
if len(input_array) <= 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 < len(left_part[0]) and right_ndx < len(right_part[0]):
counter += 1
if left_part[0][left_ndx] < 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 < len(left_part[0]):
input_array[final_ndx] = left_part[0][left_ndx]
left_ndx += 1
final_ndx += 1
counter += 1
while right_ndx < 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
```

So the output would be:

```
([1,3,4,5,6], counter)
```

您可能感兴趣的文章：

- boto3 emr client run_job_flow wants InstanceProfile attribute
- swift - How to add tab to UITabBar controller ? iOS 10
- What does the Circumflex sign/Pin/Cap operator (^) do in Elixir?
- mysql - Insert into two table in a db using mysqli php
- html - Css Bootstrap spacing issue
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?

随机阅读：

**推荐内容**-

**热点内容**-
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?
- git svn - git svn fetch does not fetch a Subversion commit message modified after initial clone
- java me - Why I am getting the bad length exception when I am running this application?
- java - How to get string.format to complain at compile time
- ruby on rails - Trigger observer of parent class on change
- python - Issue with URL pattern in Django with webmonkey tutorial