Sponsored Link •

Java Buzz Forum
Why java.util.Arrays uses Two Sorting Algorithms

0 replies on 1 page.

 Welcome Guest   Sign In

 Back to Topic List Reply to this Topic Search Forum Threaded View
 Previous Topic Next Topic
 Flat View: This topic has 0 replies on 1 page
Elliotte Rusty Harold

Posts: 1573
Nickname: elharo
Registered: Apr, 2003

 Elliotte Rusty Harold is an author, developer, and general kibitzer.
Why java.util.Arrays uses Two Sorting Algorithms Posted: Mar 30, 2013 6:47 AM

 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

 Advertisement

`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:

 John Alisson 2 Nabeel Aronowitz 3 Joe Jones 2 James Ledbetter 2 Ilya Lessing 1 Betty Lipschitz 2 Betty Neubacher 2 John Neubacher 3 Katie Senya 1 Jim Smith 3 Ping Yi 1

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:

 Ilya Lessing 1 Katie Senya 1 Ping Yi 1 John Alisson 2 Joe Jones 2 James Ledbetter 2 Betty Lipschitz 2 Betty Neubacher 2 Nabeel Aronowitz 3 John Neubacher 3 Jim Smith 3

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:

 Ilya Lessing 1 Katie Senya 1 Ping Yi 1 Betty Lipschitz 2 Betty Neubacher 2 John Alisson 2 Joe Jones 2 James Ledbetter 2 Jim Smith 3 John Neubacher 3 Nabeel Aronowitz 3

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.

 Previous Topic Next Topic

 Sponsored Links

 Web Artima.com

Copyright © 1996-2018 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use