Sort stability
You are encouraged to solve this task according to the task description, using any language you may know.
When sorting records in a table by a particular column or field, a stable sort will always retain the relative order of records that have the same key.
For example, in this table of countries and cities, a stable sort on the second column, the cities, would keep the US Birmingham above the UK Birmingham. (Although an unstable sort might, in this case, place the US Birmingham above the UK Birmingham, a stable sort routine would guarantee it).
UK London US New York US Birmingham UK Birmingham
Similarly, stable sorting on just the first column would generate “UK London” as the first item and “US Birmingham” as the last item (since the order of the elements having the same first word – “UK” or “US” – would be maintained).
The task is to examine the documentation on any in-built sort routines supplied by a language and indicate if an in-built routine is supplied, and if supplied, whether it is stable or not. (This Wikipedia table shows the stability of some common sort routines).
C++
C++ standard library's std::sort() function is not guaranteed stable. The stable analog of it is the std::stable_sort() function. In addition, std::list's sort() method is guaranteed stable.
Clojure
Clojure's sort and sort-by functions are implemented using Java's java.utils.Array.sort methods, which are guaranteed stable.
Common Lisp
Common Lisp provides the two functions sort and stable-sort.
Haskell
Haskell's sort and sortBy functions are guaranteed stable.[1]
J
J's grade primitive /: , and therefore its sort, are guaranteed stable.
From the dictionary page for /: : "Elements of /:y that select equal elements of y are in ascending order."
Java
Java's Collections.sort() and Arrays.sort() methods are guaranteed stable.
JavaScript
The ECMA standard does not specify what sorting algorithm to use, so it depends upon the implementation.
<lang javascript>ary = [["UK", "London"], ["US", "New York"], ["US", "Birmingham"], ["UK", "Birmingham"]] print(ary);
ary.sort(function(a,b){return (a[1]<b[1] ? -1 : (a[1]>b[1] ? 1 : 0))}); print(ary);
/* a stable sort will output ["US", "Birmingham"] before ["UK", "Birmingham"] */</lang>
Stable implementations:
,
,
,
UK,London,US,New York,US,Birmingham,UK,Birmingham US,Birmingham,UK,Birmingham,UK,London,US,New York
Not stable:
,
UK,London,US,New York,US,Birmingham,UK,Birmingham UK,Birmingham,US,Birmingham,UK,London,US,New York
Mathematica
Sort is not always stable. Ordering, which gives a list of indices such as to put the elements of the list in order, is stable. An example would be to sort the list (of lists) {{1, 2, 3}, {4, 5, 6}, {5, 4, 3}, {9, 5, 1}}, and doing so by looking at the 2nd value of each list: <lang Mathematica>
mylist = {{1, 2, 3}, {4, 5, 6}, {5, 4, 3}, {9, 5, 1}};
Sort[mylist, (#12 < #22) &]
#[[Ordering[#All, 2]]] &[mylist]
</lang> gives: <lang Mathematica> {{1, 2, 3}, {5, 4, 3}, {9, 5, 1}, {4, 5, 6}} {{1, 2, 3}, {5, 4, 3}, {4, 5, 6}, {9, 5, 1}} </lang> Showing that Sort is unstable, and that by using input[[Ordering[input]]] Ordering provides a way to make a stable sort.
OCaml
OCaml's List.sort and Array.sort functions are not guaranteed to be stable. The stable versions are List.stable_sort and Array.stable_sort, respectively.
Perl
The stability of Perl's in-built sort function is version-dependent. If you want to guarantee a stable sort from it, you should use the following sort pragma: <lang perl>use sort 'stable';</lang>
Python
Python's in-built sorted function as well as the sort method of lists are guaranteed stable (since version 2.3). (For even more information on the underlying routine, see [this]).
Ruby
Ruby's built-in sort methods use quicksort which is not stable[1]. <lang ruby>ary = [["UK", "London"], ["US", "New York"], ["US", "Birmingham"], ["UK", "Birmingham"]] ary.sort {|a,b| a[1] <=> b[1]}
- => [["UK", "Birmingham"], ["US", "Birmingham"], ["UK", "London"], ["US", "New York"]]</lang>
There seems to be some discussion debating whether stable sorting is worth the performance trade-off [2].
Tcl
Tcl's built-in lsort command implements a stable sort. It has been guaranteed to be stable since Tcl 8.0. Internally, it uses the mergesort algorithm.