What is the space complexity of the python sort?

by

Space complexity is defined as how much additional space the algorithm needs in terms of the N elements. And even though according to the docs, the sort method sorts a list in place, it does use some additional space, as stated in the description of the implementation:

timsort can require a temp array containing as many as N//2 pointers, which means as many as 2*N extra bytes on 32-bit boxes. It can be expected to require a temp array this large when sorting random data; on data with significant structure, it may get away without using any extra heap memory.

Therefore the worst case space complexity is O(N) and best case O(1)

More Related Contents:

  1. Is there a built in function for string natural sort?
  2. Why does “return list.sort()” return None, not the list?
  3. Sort a list by multiple attributes?
  4. What is the difference between `sorted(list)` vs `list.sort()`?
  5. Python list sort in descending order
  6. Why does ‘.sort()’ cause the list to be ‘None’ in Python? [duplicate]
  7. Why is Bubble Sort implementation looping forever?
  8. A fast way to find the largest N elements in an numpy array
  9. heapq with custom compare predicate
  10. Natural sorting
  11. Destructuring-bind dictionary contents
  12. Sort nested dictionary by value, and remainder by another value, in Python
  13. How to sort OrderedDict of OrderedDict?
  14. Find the unique values in a column and then sort them
  15. Sorting a tuple that contains tuples
  16. What is the complexity of the sorted() function?
  17. Sorting dictionary keys in python [duplicate]
  18. How to sort dictionary by key in numerical order Python
  19. Python – Delete duplicates in a dataframe based on two columns combinations?
  20. Sort filenames in directory in ascending order [duplicate]
  21. Given parallel lists, how can I sort one while permuting (rearranging) the other in the same way?
  22. Python sorting complexity on sorted list
  23. Can I sort text by its numeric value in Python?
  24. How do you sort a list in Jinja2?
  25. How can I order fields in Django ModelForm?
  26. What arguments does Python sort() function have?
  27. How can I sort a list, according to where its elements appear in another list?
  28. Sort strings by the first N characters
  29. Multi Index Sorting in Pandas
  30. Sort array’s rows by another array in Python

Leave a Comment