2

In java the collections.sort used merge sort algorithm instead of quick sort. But Arrays.sort uses quick sort. ( And i am not sure about above fact but i found this on internet like on website such as CodeRanch if they don't use that algoritjm please tell me)

Now i know average complexity of both algorithm is same. Only fact is quicksort worst is O(n^2) but that's not to common. And we are not concerned with space in today's world so it doesn't matter that merge sort is not in-place algorithm. But we concerned with stability so why we use quick sort for array.sort because its not a stable algorithm. Is it because it only concerned about integer's but i don't think that's a good reason.

Improve this question
4
  • I thought they both used TimSort. I need to check the source code. Commented Apr 22, 2015 at 0:26
  • Oh u sure i found that on internet. Commented Apr 22, 2015 at 0:27
  • 1
    @ArjunChaudhary "I found that on the internet" is pretty unhelpful. Where'd you find it? Commented Apr 22, 2015 at 0:33
  • @dimo414 there is something here to coderanch.com/t/520171/java/java/… Commented Apr 22, 2015 at 0:36

4 Answers 4

Reset to default
8

Arrays.sort uses a dual-pivot quicksort algorithm for primitive arrays only, where there is no difference between stable and unstable sorting algorithms. This is generally considered to be slightly faster but it isn't stable, so it's only used in cases where stability is irrelevant.

Arrays.sort on object arrays, and Collections.sort, use Timsort, which is a mergesort variation that does a stable sort.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

3

Your premise can be easily verified by looking at the relevant Javadocs, or even the source code. First, notice that Collections.sort(List<T>) simply delegates to Arrays.sort(Object[]) (source):

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    Object[] a = list.toArray();
    Arrays.sort(a);
    ListIterator<T> i = list.listIterator();
    for (int j=0; j<a.length; j++) {
        i.next();
        i.set((T)a[j]);
    }
}

So these two methods will have the same behavior and runtime. As noted in the documentation, the implementation is TimSort, a merge sort and insertion sort hybrid. It is guaranteed to be stable. So, sorting objects works the same whether you have an array or a collection.

What the article you link to is referring to is sorting primitive arrays. There are fewer assumptions that need to be made about primitive arrays, notably equal primitives are, by definition, indistinguishable. That means there is no need to ensure a stable sort. You'll notice the documentation for the primitive sort methods, like Arrays.sort(int[]), says nothing about the stability of these sorting methods, because such a detail is meaningless. Stability only matters when sorting data that can be equal but not identical.

Improve this answer

Comments

3

Arrays.sort does not really use the common quicksort implementation, the javadoc specifies:

The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.

Have a look at the sort algorithm located in DualPivotQuicksort; as you can see in the comments different sort algorithms are used depending on the given array.

As for the Collections sort method, it calls sort on the received implementation which (in the case I verified) delegates to Arrays.sort.

Improve this answer

Comments

-1

Arrays.sort will be slightly faster than Collections.sort because Collections.sort internally calls Arrays.sort. When dealing with primitives, stability is not relevant as primitives of same value can be rearranged without side effects. And Arrays.sort gives additional performance advantage. Hence, for primitive arrays, Arrays.sort would be preferred.

Improve this answer

2 Comments

This doesn't answer the question.
Yes actually it's about which algo they use and why?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.