This post originated from an RSS feed registered with Java Buzz by Elliotte Rusty Harold. Original Post: Why java.util.Arrays uses Two Sorting Algorithms Feed Title: The Cafes Feed URL: http://cafe.elharo.com/feed/atom/? Feed Description: Longer than a blog; shorter than a book Latest Java Buzz Posts Latest Java Buzz Posts by Elliotte Rusty Harold Latest Posts From The Cafes

java.util.Arrays uses quicksort (actually dual pivot quicksort in the most recent version) for primitive types such as int and mergesort for objects that implement Comparable or use a Comparator. Why the difference? Why not pick one and use it for all cases? Robert Sedgewick suggests that “the designer’s assessment of the idea that if a programmer’s using objects maybe space is not a critically important consideration and so the extra space used by mergesort maybe’s not a problem and if the programmer’s using primitive types maybe performance is the most important thing so we use the quicksort”, but I think there’s a much more obvious reason.

Quicksort is faster in both cases. Mergesort is stable in both cases. But for primitive types quicksort is stable too! That’s because primitive types in Java are like elementary particles in quantum mechanics. You can’t tell the difference between one 7 and another 7. Their value is all that defines them. Sort the array such [7, 6, 6, 7, 6, 5, 4, 6, 0] into [0, 4, 5, 6, 6, 6, 6, 7, 7]. Not only do you not care which 6 ended up in which position. It’s a meaningless question. The array positions don’t hold pointers to the objects. They hold the actual values of the objects. We might as well say that all the original values were thrown away and replaced with new ones. Or not. It just doesn’t matter at all. There is no possible way you can tell the difference between the output of a stable and unstable sorting algorithm when all that’s sorted are primitive types. Stability is irrelevant with primitive types in Java.

By contrast when sorting objects, including sorting objects by a key of primitive type, you’re sorting pointers. The objects themselves do have an independent nature separate from their key values. Sometimes this may not matter all that much–e.g. if you’re sorting java.lang.Strings–but sometimes it matters a great deal. To borrow an example from Sedgewick’s Algorithms I class, suppose you’re sorting student records by section:

public class Student {

  String lastname;
  String firstName;
  int section; 

}

Suppose you start with a list sorted by last name and then first name:

When you sort this again by section, if the sort is stable then it will still be sorted by last name and first name within each section:

However if you use quicksort, you’ll end up with something like this and have to resort each section by name to maintain the sorting by name:

That’s why stable sorts make sense for object types, especially mutable object types and object types with more data than just the sort key, and mergesort is such a sort. But for primitive types stability is not only irrelevant. It’s meaningless.