Is F# ResizeArray sortBy stable?

Question

Does the function ResizeArray.sortBy do a stable sort, in the sense that it does not change the order of elements which have the same value for the key function?

And if not, how to write a stable sort in F#?

Answer 1

The answer to your question is unstable.

First ResizeArray.sortBy is implemented as:

module ResizeArray =
    let sortBy f (arr: ResizeArray<'T>) = arr.Sort (System.Comparison(fun x y -> compare (f x) (f y)))

And ResizeArray is an alias for .Net List collection:

type ResizeArray<'T> = System.Collections.Generic.List<'T> // alias

Now let's look at the List documentation:

This method uses Array.Sort, which uses the QuickSort algorithm. This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal.

So unstable. If you want a stable sort, you can implement merge sort or a careful quick sort. However the stable version quick sort is less efficient.

Answer 2

Seq.sort is stable.