The Artima Developer Community
Sponsored Link

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

0 replies on 1 page.

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 0 replies on 1 page
Elliotte Rusty Harold

Posts: 1509
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 9:47 AM
Reply to this message Reply

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.

Read: Why java.util.Arrays uses Two Sorting Algorithms

Topic: Exception Handling with the Spring 3.2 @ControllerAdvice Annotation Previous Topic   Next Topic Topic: March 2013 New Java Performance Tips


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us