Collections.sort implementation

Question

I can not understand the method implementation and the logic of Collections.sort method. Here is the method implementation i found,

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]);
    }
    }

First of all this method return type is void. What is <T extends Comparable<? super T>> does in the method signature?

What is the purpose of using Array.sort here?

Also once we implement comparable or comparator where is the compare or compareTo method logic that we wrote take in to consider?

Arrays.sort is using modified quick sort algorithm to sort the array.List is converted to array and sorted using sort() method available in Arrays class.Then sorted array is put back to the orginal list.So no return type is requierd — Renjith, Jan 14 '13 at 16:43
@Renjith: `Arrays.sort(T[])` doesn't use quicksort, which isn't stable; it uses Timsort, which is a modified mergesort, really. — Louis Wasserman, Jan 14 '13 at 17:02
@Louis wasserman http://docs.oracle.com/javase/6/docs/api/java/util/Arrays.html#sort(short[]) — Renjith, Jan 14 '13 at 17:16
@Renjith: yes, it uses a modified quicksort for _numerical_ arrays, but for [_object_ arrays](http://docs.oracle.com/javase/6/docs/api/java/util/Arrays.html#sort(java.lang.Object[]))... — Louis Wasserman, Jan 14 '13 at 17:22

Tomasz Nurkiewicz · Accepted Answer · 2013-01-14T16:45:14.627

Please pay attention to where the generic type appears:

public static <T extends Comparable<? super T>> void sort(List<T> list)

It basically declares and puts restriction on generic type T. In this particular case it means: T must extend Comparable<F> where F must be of type T or a super type of it. This means thay if you have the following classes:

class Animal {}

class Dog extends Animal implements Comparable<Animal> {
    //...
}

You can still pass List<Dog> to Collections.sort() (notice that Dog implements Comparable<Animal>, not Comparable<Dog> as usual).

Arrays.sort() is used because this is where the sorting algorithm is implemented. Defensive copy from collection to array is needed to obey the contract and to avoid suboptimal runtime if collection is not random access.

Some lists, like LinkedList have poor random access (by index) performance, which makes most sorting algorithms quite slow (in the range of O(n^2)). It's better to defensively copy the whole collection and do the sorting on array because O(n + nlogn + n) is still O(nlogn) - if you get big O notation).

i still didn't get the class Dog extends Animal implements Comparable part? why cant we have class Dog extends Animal implements Comparable? — FrankD, Jan 14 '13 at 17:44
@FrankD: indeed, in most cases `Comparable` would be a better choice. But in case you implement `Comparable` for some reason, the `Collections.sort()` will still work (compile). It wouldn't if it was declaring simply `>` — Tomasz Nurkiewicz, Jan 14 '13 at 17:50

Andrei Bârsan · Answer 2 · 2013-01-14T16:49:47.207

8

The way Collections.sort works is that it actually takes the collection's underlying array, and calls its sort method to sort the actual elements. That sorting algorithm used by Java is the lightning-fast Timsort.

The method returns void because it sorts the collection in-place. That is, it modifies the collection you give it as a parameter by sorting its elements. Returning a sorted copy would be a waste of resources.

edited Jan 14 '13 at 16:49

answered Jan 14 '13 at 16:39

Andrei Bârsan

3,473
2
22
46

1

Actually, it calls the static sort method in the Arrays class. Array objects do not have their own sort method in Java. Also, the collection does not (typically/necessarily) have an "underlying array" - instead, an array is created from the collection. – Steve Kroon Mar 30 '15 at 12:56

score 2 · Answer 3 · answered Jan 14 '13 at 16:42

First of all this method return type is void

Because it's in-place implementation. List that passed to method will be sorted

What is <T extends Comparable<? super T>> does in the method signature?

To compare results that extends Comparable interface for type T and it's children.

Object[] a = list.toArray();

Convert list to plain array.

What is the purpose of using Array.sort here?

Sorting of array.

i.set((T)a[j]);

assign to list elements in sorted order from array

score 1 · Answer 4 · answered Jan 14 '13 at 16:37

1

 What is <T extends Comparable<? super T>>

This is to specify Type of T in List<T>. Read this tutorial on Type Inference.

answered Jan 14 '13 at 16:37

kosa

65,990
13
130
167

1

The [page on generic methods](http://docs.oracle.com/javase/tutorial/java/generics/boundedTypeParams.html) would probably be more appropriate. – Paul Bellora Jan 14 '13 at 16:44

score 1 · Answer 5 · answered Jan 14 '13 at 16:38

First of all this method return type is void. What is > does in the method signature?

is a generic Type that you use in your method, T could only be an object which implements java.util.Comparable.

for example if you want to pass a List<String> to the sort method it'd compile as java.lang.String implements java.lang.Comparable, but if you pass List<Animal> you'd get a compiler error unless Animal implements java.lang.comparable

Collections.sort implementation

5 Answers5

Linked