title: How python decides when to call the comparator while sorting?
body: <p>I have a small script to print a message whenever the comparator is called</p>
  <pre class="lang-py prettyprint-override"><code>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)
  </code></pre>
  <p>Output:</p>
  <pre><code>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]
  </code></pre>
  <p>You can see that for the same input size the number of times comparators are called are different for the 4 cases.</p>
  <p>Can someone help me understand how python decides when or when not to call the comparator?</p>
  <p>Also, let me know the best, average and worst case time complexities</p>