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?

Solution 1

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).

Solution 2

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.

Solution 3

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

Solution 4

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

Solution 5

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

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

View more solutions

Comments

[Paul Bellora]

The page on generic methods would probably be more appropriate.

[FrankD]

i still didn't get the class Dog extends Animal implements Comparable<Animal> part? why cant we have class Dog extends Animal implements Comparable<Dog>?

[Tomasz Nurkiewicz]

@FrankD: indeed, in most cases Comparable<Dog> would be a better choice. But in case you implement Comparable<Animal> for some reason, the Collections.sort() will still work (compile). It wouldn't if it was declaring simply <T extends Comparable<T>>

[Steve Kroon]

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.

[rogerdpack]

Which contract would you say here?