# What is stable sorting?

Created May 4, 2012

**Avi Kak**

The collections framework specification requires that the sorting algorithms be stable. Stated succinctly, a sorting algorithm is stable if it does not reorder equal elements. But what does that really mean? The goal of this posting is to illustrate this concept.

Stability in sorting becomes an issue for class-type objects with two or more data members. We'd obviously need to choose a data member whose values will be used to order the objects for sorting. Let's say we have multiple objects in a list whose values for the data member chosen for comparison are the same, but whose values for the other data members are different. A stable sorting algorithm will leave the original order of such objects untouched.

Stability in sorting, or lack thereof, is best illustrated by comparing the sorted order obtained through the quicksort algorithm with the sorted order obtained through the mergesort algorithm. An optimized implementation of quicksort is slightly faster than an optimized implementation of mergesort but does not guarantee stability. On the other hand, mergesort guarantees stability.

To show the comparative results obtained with quicksort and mergesort, let's define the following class:

class Person { String name; int rank; Person( String nam, int r ) { name = new String( nam ); rank = r; } String getName() { return name; }; public String toString() { return name + " " + rank; } }We will sort

*Person*

*objects by using the following**Comparator**object:*class PersonComparator implements Comparator { public int compare( Object o1, Object o2 ) { Person p1 = ( Person ) o1; Person p2 = ( Person ) o2; return p1.getName().compareTo( p2.getName() ); } }This will compare

*Person**objects on the basis of the**name**field. For the purpose of sorting, let's now construct a list of**Person**objects by*List perList = new ArrayList(); perList.add( new Person( "Zaphod", 0 ) ); perList.add( new Person( "Zaphod", 1 ) ); perList.add( new Person( "Zaphod", 2 ) ); perList.add( new Person( "Betelgeuse", 0 ) ); perList.add( new Person( "Betelgeuse", 1 ) ); perList.add( new Person( "Betelgeuse", 2 ) ); perList.add( new Person( "Trillion", 0 ) ); perList.add( new Person( "Trillion", 1 ) ); perList.add( new Person( "Trillion", 2 ) );A stable sorting algorithm will reorder the names in the list, but for each name will leave untouched the order of appearance with respect to the rank. We can sort this list by a mergesort algorithm by invoking

Collections.sort( perList, new PersonComparator() );The sorted listed will be as follows:

Betelgeuse 0 Betelgeuse 1 Betelgeuse 2 Trillion 0 Trillion 1 Trillion 2 Zaphod 0 Zaphod 1 Zaphod 2where the name is followed by the associated rank in each

*Person**object.*
On the other hand, if we sort the same original list with a quicksort
algorithm using again the *name field for comparison, we get
*

Betelgeuse 0 Betelgeuse 2 Betelgeuse 1 Trillion 2 Trillion 0 Trillion 1 Zaphod 0 Zaphod 2 Zaphod 1

*Notice that objects that are equal with respect to the**name**field are getting shuffled by the quicksort algorithm.*
The quicksort results I showed above were obtained with a C++ program
that invoked the well-known *qsort function with the following
invocation
*

qsort( perList, 9, sizeof( Person* ), comparePersons );

*where the list of**Person**objects was declared as*Person* perList[9];with each element of the list instantiated by a statement like

perList[0] = new Person( "Zaphod", 0 ); perList[1] = new Person( "Zaphod", 1 ); ... ...The comparison function needed for the fourth argument of

*qsort**was defined by*int comparePersons( const void* arg1, const void* arg2 ) { string str1 = (*( Person** )arg1)->name; string str2 = (*( Person** )arg2)->name; return ( str1 ).compare( str2 ); }

*
*