Why Collections.sort is using merge sort insteadof quicksort?

Hi,

We know that quick sort is the best sorting algorithm.

The collections.sort used merge sort algorithm instead of quick sort. But Arrays.sort uses quick sort.

What is the reason Collections.sort uses merge sort instead of quick sort?

Hi,

I'm not sure if quicksort is the best sorting algo. Merge sort is also very fast. And I found this in wikipedia: "Merge sort is more efficient than quick sort for some types of lists if the data to be sorted can only be efficiently accessed sequentially".

Anyway, since quicksort may be better than merge sort when operating on a array-like data type, it is used implemented in Arrays. But when the assumption about array-like data type cannot be made (as in the case of Collection), merge sort seems like a safer bet

Hi,

We can't measure the performance of an sorting algorithm based on "how we access the elements".

Thennam Pandian wrote:We can't measure the performance of an sorting algorithm based on "how we access the elements".

Why not?

The main reason why mergesort is used in Collections.sort is that mergesort is stable - it does not reorder elements that are equal. Look up "stable sort" on Wikipedia if you don't understand the consequences.

On the other hand, Arrays.sort is used to sort primitives. Here the stability of the sort is meaningless, as you cannot distinguish two values that are equal. Hence, quicksort is used (except when sorting an array of Objects, for which mergesort is performed). Moreover, quicksort can be done in place, so there is no need to allocate another array.

Mergesort's ability to efficiently sort sequentially accessed data is of no real use in Java. This feature is used when sorting data so large that they don't fit to memory and must be written to disk. Even if you sort a linked list, which cannot be accessed randomly, Java creates an array-based copy, sorts it and repopulates the list from this copy.