CODEWITHSUNDEEP
javaarraysalgorithmsorting
user590444
user590444

Reputation: 4332

Why use two different algorithm for sorting arrays?

In the Arrays class quick sort is used for sorting primitives but for sorting objects, it's merge sort.

I wonder why this is so?

Upvotes: 10

Views: 482

Answers (2)

Paŭlo Ebermann
Paŭlo Ebermann

Reputation: 74800

The reason for using mergesort is that they want a stable algorithm - e.g. where equal objects (by compareTo() or compare()) are at the same relative order as before.

For primitives, equality implies "non-distinguish-ability". When sorting {5, 3, 5} to {3, 5, 5} it does not matter which of the fives was the first one before. So we can use the quicker (and non-stable) quicksort algorithm here.

Upvotes: 14

MarcB
MarcB

Reputation: 559

Just a guess, but quicksort is O(n^2) in the worst case, while merge sort is stable (guaranteed O(n log n)).

The worst case for quicksort is triggered by equal values.. and equal primitives are identical, while "equal" objects may not be.

Upvotes: 1

Related Questions