Stable sort - do we really need it?

Question

I do not understand the underlying problem that tries to solve the stable sorting algorithm.

Arrays.sort(Object[]) Javadoc states:

This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

But if elements are equal, they are not distringuishable from each other! If you swap two equal elements, this should not affect anything. This is the definition of equality.

So, why do we need stability at all?

UPDATE: My question is about Collections.sort(List<T>) / Objects.sort(Object[]) methods, not Collections.sort(List<T>, Comparator<T>), Objects.sort(Comparator<T>). The latter ones are bit different. But there is still no need for stability for them: if you want predictable compound sorts, then you create appropriate compound comparators.

Answer 1

Let's say you have two columns. Column name and column date. Then you start ordering your list by date first, afterwards you sort them by name. If your sort is stable what it will produce is that you get the name ordered correctly and if the names are equal you get them sorted by date since your order is stable. But if your order is not stable you won't have any relative ordering between the equal keys.

public static void main (String[] args) 
{
    // your code goes here
    List<FirstNameLastName> list = new ArrayList<FirstNameLastName> ();
    list.add(new("A","B"));
    list.add(new("D","B"));
    list.add(new("F","B"));
    list.add(new("C","C"));
    list.add(new("E","C"));
    list.add(new("B","C"));

    Arrays.sort(list,new Comparator(firstName)); //FIXME
    // A-B , B-C , C-C , D-B , E-C  , F-B
    Arrays.sort(list,new Comparator(lastName)); //FIXME
    // A-B , D-B F-B,B-C,C-C,E-C
    //So as you see here inside the last name B and C each first name 
    //is sorted also

    //However if you just sorted instead directly on last name only
    //A-B , D-B -F,B-C-C,E-C,B-C
}

private class FirstNameLastName {
      String firstName;
      Stirng lastName;
      public FirstNameLastName(String firstName,String lastName) {
          this.firstName = firstName;
          this.lastName = lastName;
       }
 }

Answer 2

Unstable sort can suck for UIs. Imagine you are using file explorer in Windows, with a details view of songs. Can you imagine if you kept clicking filetype column to sort by filetype, and it randomly reordered everything within each type-group every time you clicked it?

Stable sort in UI's allows me (the user) to create my own compound sorts. I can chain multiple sorts together, like "sort by name", then "sort by artist", then "sort by type". The final resulting sort prioritizes type, then artist, and then finally, by name. This is because a stable sort actually preserves the previous sort, allowing me to "build" my own sorting from a series of elementary sorts! Whereas unstable sorts nuke the previous sort type's results.

Of course, in code, you'd just make one big, fully defined ordering, and then sort and sort once, rather than a chained "compound" sort like I described above. This is why you tend not to need stable sorts for most application-internal sorting. But when the user drives the click-by-click, stable sorting is the best/simplest.

EDIT: "My question is about Collections.sort(List<T>) / Objects.sort(Object[]) methods"

These are generic sorts that work on anything that defines Comparable. Your class's Comparable implementation might return 0 even when the objects are not technically "equal", because you might be trying for a particular ordering. In other words, these methods are every bit as open to custom orderings as Collections.sort(List<T>, Comparator<T>). And you might want stable sort, or you might not.

Answer 3

Consider the example

[{1, 'c'}, {2, 'a'}, {3, 'a'}] 

It is sorted by number field, but not by character. After a stable sort by character:

[{2, 'a'}, {3, 'a'}, {1, 'c'}] 

After an unstable sort the following order is possible:

[{3, 'a'}, {2, 'a'}, {1, 'c'}] 

You can notice that {3, 'a'} and {2, 'a'} were reordered.

Java 8 example (Java API has only stable sort for objects):

List<Point> list = Arrays.asList(new Point(1,1), new Point(1,0), new Point(2,1));
list.sort((a,b) -> Integer.compare(a.x,b.x));
System.out.println(list);
list.sort((a,b) -> Integer.compare(a.y,b.y));
System.out.println(list);

Answer 4

You may (and almost always do) have elements for which it is true that:

a.compareTo(b) == 0 and
a.equals(b) == false

Take, for example, a List<Product>, where product has a number of properties: - id - price

You could see several use cases where you would want to sort Product by id or price but not by other values.

The big benefit that stable sorting brings to the table is that if you sort by price then by id you will have a List that is correctly sorted by first price then by id.

If your sorting algorithm is unstable, then the second sort by id might be break the order of the initial sort by price.