The implementation has been the same for decades, but it’s still explainable as forward-compatibility: by making the call that expresses what you most care about with the call, you can continue to get that result in the future when the library is updated to take advantage of some new sorting algorithm. Or newly usable algorithm, say from new specialization over element ranges and lengths of list; APLs have some wild input-sensitive optimizations. There’s some hint of this in the following comment at the link, which used an array_to_list_in_place. If later the stdlib gets a much faster sort that isn’t stable, your program using List.stable_sort will not care about the introduced instability, but your program using List.fast_sort will benefit immediately.
Yes, but I’m not talking about List.stable_sort. As I said, neither List.sort nor List.fast_sort are (guaranteed) to be stable.
It is clear to me when I should use List.stable_sort: Whenever I need the sorting to be stable. But it is not entirely clear when to pick List.sort over List.fast_sort or the other way around.
My assumption is that List.fast_sort may consume more memory and that is the reason why I would normally resort to List.sort. Is that right?
List.sort is guaranteed to run in constant heap space (in addition to the size of the result list) and logarithmic stack space.
and List.fast_sort’s is merely that it’s fastest for typical inputs. So yes the straightforward reading is that List.fast_sort may have less desirable heap or stack usage.
Maybe a small note like, “May have higher memory consumption than List.sort in future implementations.” for List.fast_sort’s documentation would make it a bit easier to understand. (Though I guess it is already unambiguous as is, but still a bit confusing.)
