I understand your point but, at least from the perspective of the user of a programming language, 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 wasn't proposing to change Scala's implementation, just trying to understand why there's only one if there are so many containers with wildly different behaviours.

If you're curious, as far as i know this is still Python's sorting algorithm: timsort

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!

## re: Microbenchmarking your Scala Code VIEW POST

TOP OF THREAD FULL DISCUSSIONI understand your point but, at least from the perspective of the user of a programming language, 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 wasn't proposing to change Scala's implementation, just trying to understand why there's only one if there are so many containers with wildly different behaviours.

If you're curious, as far as i know this is still Python's sorting algorithm: timsort

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 :)