dcsimg

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  2
where 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 );
}