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