CODEWITHSUNDEEP
javasortingcollections
FrankD
FrankD

Reputation: 899

Collections.sort implementation

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?

Upvotes: 10

Views: 25689

Answers (5)

Andrei B&#226;rsan
Andrei B&#226;rsan

Reputation: 3523

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.

Upvotes: 8

Tomasz Nurkiewicz
Tomasz Nurkiewicz

Reputation: 340713

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

Upvotes: 20

mishadoff
mishadoff

Reputation: 10789

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

Upvotes: 2

PermGenError
PermGenError

Reputation: 46398

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

Upvotes: 1

kosa
kosa

Reputation: 66637

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

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

Upvotes: 1

Related Questions