
Sorting Algorithm

This is a sorting algorithm.   It may be applied to a set of data in order to sort it.    
For comparing various sorts, see compare sorts.  
For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts
Heap sort |
Merge sort |
Patience sort |
Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort


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.



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



Task

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


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




mylist = {{1, 2, 3}, {4, 5, 6}, {5, 4, 3}, {9, 5, 1}};
Sort[mylist, (#1[[2]] < #2[[2]]) &]
#[[Ordering[#[[All, 2]]]]] &[mylist]