My professional interests are cloud and big data technologies, machine learning, and software development. I like to read source code and research papers to understand how stuff works.
Pronoun: He
the expectation is (going to use Python's syntax here) that "mutablelist.sort()" or "immutablelist.sort()" or and so on are going to choose a different sorting algorithm, for each type of the caller.
I'm not sure about whether one should have this expectation. The problem is that there are so many different possible implementations of a value sequence and so many different sorting algorithms. How would you possibly know what is the best sorting algorithm when designing the library? It might not only depend on the data structure but also the data itself. The strategy to have a general-purpose algorithm in your library that works everywhere is not a bad one IMHO. It will be good enough for all the cases where performance does not matter. If performance matters you anyway have to put some thought into picking the right data structure and right sorting algorithm.
just trying to understand why there's only one if there are so many containers with wildly different behaviours.
I don't know but I could imagine that it's good enough like this. Maybe the development focus of the language was just different and nobody complained / made an effort to change it.
This is also indicated by the documentation of scala.util.Sorting: "Note also that high-performance non-default sorts for numeric types are not provided. If this is required, it is advisable to investigate other libraries that cover this use case."
So it seems that if you need fast sorting, stick to arrays. If this is not fast enough, try a different library.
If you're curious, as far as i know this is still Python's sorting algorithm: timsort
Java > 6 also uses timsort for sorting arrays of objects (still quick sort for primitives afaik). But does Python have different data structures or only arrays? What happens if you try to call timsort on a linked list in Python? (sorry if my question is stupid but I didn't use Python a lot).
Thanks a lot for the discussion :) It's a lot of fun to dig deeper!
My professional interests are cloud and big data technologies, machine learning, and software development. I like to read source code and research papers to understand how stuff works.
Pronoun: He
I'm not sure about whether one should have this expectation. The problem is that there are so many different possible implementations of a value sequence and so many different sorting algorithms. How would you possibly know what is the best sorting algorithm when designing the library? It might not only depend on the data structure but also the data itself. The strategy to have a general-purpose algorithm in your library that works everywhere is not a bad one IMHO. It will be good enough for all the cases where performance does not matter. If performance matters you anyway have to put some thought into picking the right data structure and right sorting algorithm.
I don't know but I could imagine that it's good enough like this. Maybe the development focus of the language was just different and nobody complained / made an effort to change it.
This is also indicated by the documentation of scala.util.Sorting: "Note also that high-performance non-default sorts for numeric types are not provided. If this is required, it is advisable to investigate other libraries that cover this use case."
So it seems that if you need fast sorting, stick to arrays. If this is not fast enough, try a different library.
Java > 6 also uses timsort for sorting arrays of objects (still quick sort for primitives afaik). But does Python have different data structures or only arrays? What happens if you try to call timsort on a linked list in Python? (sorry if my question is stupid but I didn't use Python a lot).
Thanks a lot for the discussion :) It's a lot of fun to dig deeper!
Python's main container structures are immutable arrays (tuples) and mutable arrays (lists).
I don't know all the details of the implementation but they are both C arrays.
Lists: How are lists implemented? and this
Tuples: stackoverflow.com/a/14135893/4186181
Thank you for the discussion! :-)
I see. I learned a lot during the writing and discussion process :)