How python decides when to call the comparator while sorting?-CodePudding

I have a small script to print a message whenever the comparator is called

from functools import cmp_to_key

def compare(a, b):
  print('comparator called')
  return a - b
  
mylist = [5, 1, 2, 4, 3]
sorted_list = sorted(mylist, key=cmp_to_key(compare))
print(sorted_list)


mylist = [1, 2, 3, 4, 5]
sorted_list = sorted(mylist, key=cmp_to_key(compare))
print(sorted_list)


mylist = [5, 4, 3, 2, 1]
sorted_list = sorted(mylist, key=cmp_to_key(compare))
print(sorted_list)


mylist = [5, 1, 2, 3, 4]
sorted_list = sorted(mylist, key=cmp_to_key(compare))
print(sorted_list)

Output:

comparator called
comparator called
comparator called
comparator called
comparator called
comparator called
comparator called
comparator called
[1, 2, 3, 4, 5]
comparator called
comparator called
comparator called
comparator called
[1, 2, 3, 4, 5]
comparator called
comparator called
comparator called
comparator called
[1, 2, 3, 4, 5]
comparator called
comparator called
comparator called
comparator called
comparator called
comparator called
comparator called
comparator called
[1, 2, 3, 4, 5]

You can see that for the same input size the number of times comparators are called are different for the 4 cases.

Can someone help me understand how python decides when or when not to call the comparator?

Also, let me know the best, average and worst case time complexities

CodePudding user response：

Python's default sort is a Tim sort, which is a combination of both merge sort and insertion sort.

The code is here.

More info about the sorting algorithm here

Complexity:

Worst & Average case: O(n log n)
Best case: It occurs when there is no sorting required, O(n)