Sort stability

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

1. Examine the documentation on any in-built sort routines supplied by a language.
2. Indicate if an in-built routine is supplied
3. If supplied, indicate whether or not the in-built routine is stable.

(This Wikipedia table shows the stability of some common sort routines).

AutoHotkey

Autohotkey has got a build-in sorting method for tables, which is stable. <lang AutoHotkey>Table = ( UK, London US, New York US, Birmingham UK, Birmingham )

Gui, Margin, 6 Gui, -MinimizeBox Gui, Add, ListView, r5 w260 Grid, Orig.Position|Country|City Loop, Parse, Table, `n, `r {

   StringSplit, out, A_LoopField, `,, %A_Space%
   LV_Add("", A_Index, out1, out2)

} LV_ModifyCol(1, "77 Center") LV_ModifyCol(2, "100 Center") LV_ModifyCol(3, 79) Gui, Add, Button, w80, Restore Order Gui, Add, Button, x+10 wp, Sort Countries Gui, Add, Button, x+10 wp, Sort Cities Gui, Show,, Sort stability Return

GuiClose: GuiEscape: ExitApp

ButtonRestoreOrder:

   LV_ModifyCol(1, "Sort")

Return

ButtonSortCountries:

   LV_ModifyCol(2, "Sort")

Return

ButtonSortCities:

   LV_ModifyCol(3, "Sort")

Return</lang>

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.

C#

The .NET library documentation for Array.Sort() says that it uses quicksort and is unstable.[1]

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.

D

In the std.algorithm Phobos v.2 module there is SwapStrategy that defines the swapping strategy for algorithms like sort and partition.

Unstable, stable and semistable (in algorithms that partition ranges in two, semistable preserves stability on just the left of the partition point) are supported.

Factor

The sorting vocabulary implements a stable sort. sorting docs

F#

Array.sort is not stable. List.sort and Seq.sort are stable.

GAP

<lang gap># According to section 21.18 of the reference manual, Sort is not stable (it's a Shell sort).

1. However, SortingPerm is stable. We will see it on an example, showing indexes of elements after the sort.

n := 20; L := List([1 .. n], i -> Random("AB"));

1. "AABABBBABBABAABABBAB"

p := SortingPerm(L);

1. (3,10,15,17,18,19,9,14,7,13,6,12,16,8,4)(5,11)

a := Permuted(L, p);; b := Permuted([1 .. n], p);;

PrintArray(TransposedMat(List([1 .. n], i -> [a[i], b[i]])));

1. [ [ 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B' ],
2. [ 1, 2, 4, 8, 11, 13, 14, 16, 19, 3, 5, 6, 7, 9, 10, 12, 15, 17, 18, 20 ] ]</lang>

Go

Comments in sort.go of the standard library read,

// Quicksort, following Bentley and McIlroy,
// ``Engineering a Sort Function,'' SP&E November 1993.

There is no mention of stability. Presumably it is unstable.

Haskell

Haskell's sort and sortBy functions are guaranteed stable.[2]

Icon and Unicon

Icon and Unicon use Quick Sort internally. As described in The Implementation of Icon and Unicon: a Compendium] sorting is done by the standard C library routine qsort which is not guaranteed to be stable.

Note(1): The built-in sort handles lists of mixed types by sorting first by type and then value. No coercion of types is performed. The sort order of types is: &null, integer, real, string, cset, procedure, list, set, table, record.

J

J's grade primitive /:, and therefore its sort (such as /:~), 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:

Works with: SpiderMonkey version 1.8

Works with: Firefox version 3

Works with: Internet Explorer version 6

Works with: JScript version 5.7

Works with: OSSP js

UK,London,US,New York,US,Birmingham,UK,Birmingham
US,Birmingham,UK,Birmingham,UK,London,US,New York

Not stable:

Works with: Rhino version 1.7 rel 2

Works with: Google Chrome version 3.0

UK,London,US,New York,US,Birmingham,UK,Birmingham
UK,Birmingham,US,Birmingham,UK,London,US,New York

Lua

The built-in function table.sort is not guaranteed stable.

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) &]

1. [[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.

MATLAB

MathWorks' policy seems to be that their built-in sorting algorithm will always be a stable sort across all versions (reference). To check to see if your version of MATLAB provides a stable sort type "sort" into the command line. Then highlight the text and right-click it and select "Open Selection" in the pop-up menu. This will open the source code for the sort function, the comments of which should tell you if the sort algorithm they use is stable.

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.

Oz

Oz' Sort function is not guaranteed to be stable in the documentation.

However, internally it uses Merge sort and in practice is stable if a reflexive ordering is used, e.g. Value.'=<' or Value.'>='.

Example: <lang oz>declare

 Cities = ['UK'#'London'
           'US'#'New York'
           'US'#'Birmingham'
           'UK'#'Birmingham']

in

 %% sort by city; stable because '=<' is reflexiv
 {Show {Sort Cities fun {$ A B} A.2 =< B.2 end}}

 %% sort by country; NOT stable because '<' is not reflexiv
 {Show {Sort Cities fun {$ A B} A.1 < B.1 end}}</lang>

PARI/GP

Pari's vecsort is stable.

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>

Perl 6

The sort built-in (available as sub and method) is stable.

Short demonstration for sorting only on the second item of each array: <lang perl6>use v6; my @cities =

   ['UK', 'London'],
   ['US', 'New York'],
   ['US', 'Birmingham'],
   ['UK', 'Birmingham'],
   ;

.say for @cities.sort: { .[1] };</lang>

PHP

PHP uses QuickSort for most of its sort functions so it is unstable. [3]

PicoLisp

The sort function is unstable

PureBasic

PureBasic's includes two built-in sort functions for arrays, SortArray() and SortStructuredArray(), and two built-in sort functions for linked lists, SortList() and SortStructuredList(). Sorting of linked lists is stable and uses a merge-sort, while sorting for arrays is unstable and uses a quicksort.

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

R

R uses shell sort (stable) or quick sort (unstable). An easy way to show the difference is names to vector entries, then check if names are still ordered after sorting.

<lang R>

1. First, define a bernoulli sample, of length 26.

x <- sample(c(0, 1), 26, replace=T)

x

1. [1] 1 1 1 1 0 1 1 0 1 0 1 1 1 0 1 1 0 1 0 1 0 1 1 0 1 0

1. Give names to the entries. "letters" is a builtin value

names(x) <- letters

x

1. a b c d e f g h i j k l m n o p q r s t u v w x y z
2. 1 1 1 1 0 1 1 0 1 0 1 1 1 0 1 1 0 1 0 1 0 1 1 0 1 0

1. The unstable one, see how "a" appears after "l" now

sort(x, method="quick")

1. z h s u e q x n j r t v w y p o m l a i g f d c b k
2. 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1. The stable sort, letters are ordered in each section

sort(x, method="shell")

1. e h j n q s u x z a b c d f g i k l m o p r t v w y
2. 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

</lang>

REBOL

<lang rebol>; REBOL's sort function is not stable by default. You need to use a custom comparator to make it so.

blk: [

   [UK London]
   [US New-York]
   [US Birmingham]
   [UK Birmingham]

] sort/compare blk func [a b] [either a/2 < b/2 [-1] [either a/2 > b/2 [1] [0]]]

Note that you can also do a stable sort without nested blocks.

blk: [

   UK London
   US New-York
   US Birmingham
   UK Birmingham

] sort/skip/compare blk 2 func [a b] [either a < b [-1] [either a > b [1] [0]]]</lang>

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]}

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].

Scala

Works with: Scala version 2.8

There are two sort methods defined on Seq, which is the base collection trait for all sequences. The methods are sortWith and sortBy, and differ only on the argument used. The first expects a function that will implement the "less than" method for the type of the sequence. The second expects a function from the type of the sequence into any type for which there is an Ordering, plus an implicit Ordering of the proper type.

The sort is stable.

Examples: <lang scala>scala> val list = List((1, 'c'), (1, 'b'), (2, 'a')) list: List[(Int, Char)] = List((1,c), (1,b), (2,a))

scala> val srt1 = list.sortWith(_._2 < _._2) srt1: List[(Int, Char)] = List((2,a), (1,b), (1,c))

scala> val srt2 = srt1.sortBy(_._1) // Ordering[Int] is implicitly defined srt2: List[(Int, Char)] = List((1,b), (1,c), (2,a))

scala> val cities = """

    | |UK  London
    | |US  New York
    | |US  Birmingham
    | |UK  Birmingham
    | |""".stripMargin.lines.filterNot(_ isEmpty).toSeq

cities: Seq[String] = ArrayBuffer(UK London, US New York, US Birmingham, UK Birmingham)

scala> cities.sortBy(_ substring 4) res47: Seq[String] = ArrayBuffer(US Birmingham, UK Birmingham, UK London, US New York)</lang> Besides that, there is the object scala.util.Sorting, which provides quickSort and stableSort. The former is only provided on Array, but the latter is provided over both Array and Seq. These sorts operate in-place, with the one over Seq returning a sorted Array. Here is one example: <lang scala>scala> val cityArray = cities.toArray cityArray: Array[String] = Array(UK London, US New York, US Birmingham, UK Birmingham)

scala> scala.util.Sorting.stableSort(cityArray, (_: String).substring(4) < (_: String).substring(4))

scala> cityArray res56: Array[String] = Array(US Birmingham, UK Birmingham, UK London, US New York)</lang>

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.