How python decides when to call the comparator while sorting?

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

>Solution :

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)