Python sorting complexity on sorted list

by

This is entirely implementation dependent. All that python guarantees is that the builtin sorting algorithm is stable (elements which compare equal retain their relative ordering). An implementation could even use a stable bubble sort if it wanted to …

Cpython uses TimSort (a hybrid of insertion sort an mergesort) which I believe has O(N) complexity if the input is already sorted — It picks up the best case performance of insertion sort and the worst case performance of mergesort (O(NlogN)).

And if you’re curious about the implementation, the source code has a very nice description.

More Related Contents:

  1. Is there a built in function for string natural sort?
  2. Sort a list by multiple attributes?
  3. What is the difference between `sorted(list)` vs `list.sort()`?
  4. Python list sort in descending order
  5. sort() and reverse() functions do not work
  6. How to sort a list of strings numerically?
  7. Why does ‘.sort()’ cause the list to be ‘None’ in Python? [duplicate]
  8. Naturally sorting Pandas DataFrame
  9. Why is Bubble Sort implementation looping forever?
  10. heapq with custom compare predicate
  11. Natural sorting
  12. How to sort a list by length of string followed by alphabetical order?
  13. Sort nested dictionary by value, and remainder by another value, in Python
  14. How can I reorder a list? [closed]
  15. How to sort OrderedDict of OrderedDict?
  16. Find the unique values in a column and then sort them
  17. Sort a list of lists with a custom compare function
  18. Sorting a tuple that contains tuples
  19. What is the complexity of the sorted() function?
  20. Sorting dictionary keys in python [duplicate]
  21. How to sort dictionary by key in numerical order Python
  22. Sort filenames in directory in ascending order [duplicate]
  23. Given parallel lists, how can I sort one while permuting (rearranging) the other in the same way?
  24. Efficiently sorting a numpy array in descending order?
  25. How can I order fields in Django ModelForm?
  26. sorting list of nested dictionaries in python
  27. What is this odd sorting algorithm?
  28. Custom sort python [duplicate]
  29. Rearranging list based on order of another list
  30. Finding Nth item of unsorted list without sorting the list

Leave a Comment