Discussion on quick sort

[D.J. Quavern]

Dear ranchers,

I am writing a report on java quicksort and comparing it to mine. I have to come with explanations about which ameliorations makes java quicksort so performant against a home made version.

I tried to read the source code which is thousands rows long and could not find obvious ameliorations: I wrote about:
- insertion sort threeshold (47), the merge sort threeshold (286);
- that java had been using empirical tests to choose a pivot (explanations at row 296)
- that java uses pair insertion sort.

What else do you recommend I should be mentioning in my report? I don't really know what makes a difference in performance.

[Tim Moores]

The classic book "Algorithms & Data Structures" by Wirth is available for free online (see https://coderanch.com/wiki/660152/Find-Links-Free-Stuff for a link) - it has a section on sorting that discusses all kinds of algorithms, including QuickSort. That should be of interest.

[Kaustubh Bansal]

Java internally uses dual pivot quicksort.
Apart from that, there are multiple different thresholds where either insertion sort, merge sort or the above variant of quicksort is used.
The best way to understand the special cases is to read the code and focus on comments.

The following paper will give more details on dual pivot quicksort
https://codeblab.com/wp-content/uploads/2009/09/DualPivotQuicksort.pdf

[Stephan van Hulst]

Java only uses quicksort for primitive element types. For collections and arrays of reference types, Java uses a variant of mergesort.

[Michael Krimgen]

Java uses TimSort for Objects: https://en.wikipedia.org/wiki/Timsort

[D.J. Quavern]

Thank you everybody, that was a lot of threads to follow to make a better report

[Campbell Ritchie]

Michael Krimgen wrote:Java uses TimSort for Objects: . . .

I presume you know why? That is the same as the modified merge sort Stephan mentioned.

[D.J. Quavern]

Campbell Ritchie wrote:

Michael Krimgen wrote:Java uses TimSort for Objects: . . .

I presume you know why? That is the same as the modified merge sort Stephan mentioned.

No, I don't know anything except the the information from Wikipedia. Is there a special reason except it's more efficient?

[Stephan van Hulst]

The reason is that quicksort is unstable. If you have a few elements in the array that are considered equal, quicksort may rearrange them relative to each other. For primitive values this doesn't really matter, because values that are equal are also identical.

For instance, if you sort [3, 1, 3, 2] to [1, 2, 3, 3], it doesn't really matter if the threes in the last positions originally came from indices 0 and 2 respectively, or indices 2 and 0 respectively.

For objects it does matter. Even when two objects are equal to each other, they may have a separate identity. Consider the following code:

final class MutablePerson implements Comparable<MutablePerson> {

  private String name;

  MutablePerson(String name) {
    setName(name);
  }

  void setName(String name) {
    if (name == null)
      throw new IllegalArgumentException();

    this.name = name;
  }

  @Override
  public int compareTo(MutablePerson other) {
    return this.name.compareTo(other.name);
  }

  @Override
  public boolean equals(Object other) {
    return other instanceof MutablePerson && this.compareTo((MutablePerson) other) == 0;
  }

  @Override
  public int hashCode() {
    return name.hashCode();
  }

  @Override
  public String toString() {
    return name;
  }
}

var persons = new MutablePerson[] {
  new MutablePerson("Carol"),
  new MutablePerson("Alice")
  new MutablePerson("Bob"),
  new MutablePerson("Alice")
  new MutablePerson("Dave")
};

var aliceOne = persons[2];
var aliceTwo = persons[4];

Arrays.sort(persons);

// This obviously prints [Alice, Alice, Bob, Carol, Dave]
System.out.println(Arrays.toString(persons));

aliceOne.setName("Eve");

 // Does this print  [Eve, Alice, Bob, Carol, Dave],
 // or does it print [Alice, Eve, Bob, Carol, Dave]?
System.out.println(Arrays.toString(persons));

Because mergesort is a stable sorting algorithm it is guaranteed that after sorting the array, aliceOne must come before aliceTwo, and therefore changing the name of aliceOne will result in [Eve, Alice, Bob, Carol, Dave]. With quicksort you don't have this guarantee, so it's not used for arrays of objects.

[D.J. Quavern]

Thank you!
Even though it was very clear, I don't get why you did not have this garantee for quicksort? If aliceOne is in the right position in the array, the name should be changed easily to Eve even with quicksort?

[Stephan van Hulst]

D.J. Quavern wrote:If aliceOne is in the right position in the array

What's the right position of aliceOne in the array after sorting?

[D.J. Quavern]

Stephan van Hulst wrote:

D.J. Quavern wrote:If aliceOne is in the right position in the array

What's the right position of aliceOne in the array after sorting?

I would have said first but I suspect that I am supposed -since you are asking- to reply second since quicksort works with swaps?

[D.J. Quavern]

Stephan van Hulst wrote:
Because mergesort is a stable sorting algorithm it is guaranteed that after sorting the array, aliceOne must come before aliceTwo, and therefore changing the name of aliceOne will result in [Eve, Alice, Bob, Carol, Dave]. With quicksort you don't have this guarantee, so it's not used for arrays of objects.

You write that I don't have this guarantee, but it's still possible?

[Campbell Ritchie]

It might leave those two elements in their original positions and it might not. That behaviour may vary between implementations and it may vary if you have a different size array. I don't know a lot about quicksort, I am afraid.

[Stephan van Hulst]

For unstable sorting algorithms, like quicksort, the final position of elements that have an equal somewhere else in the array is undefined.

That's why when the exact ordering is important, you absolutely need to use a stable algorithm, like mergesort. It's possible to make a stable quicksort, but it either:

requires more memory, or

it won't be quick.

[D.J. Quavern]

Thank you a lot. I get it now!