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
– Renjith, Commented Jan 14, 2013 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
– Louis Wasserman, Commented Jan 14, 2013 at 17:02
@Louis wasserman docs.oracle.com/javase/6/docs/api/java/util/… — Renjith
– Renjith, Commented Jan 14, 2013 at 17:16
@Renjith: yes, it uses a modified quicksort for numerical arrays, but for object arrays... — Louis Wasserman
– Louis Wasserman, Commented Jan 14, 2013 at 17:22

Tomasz Nurkiewicz · Accepted Answer · 2013-01-14 16:45:14Z

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<Animal> part? why cant we have class Dog extends Animal implements Comparable<Dog>?
@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>>

Andrei Bârsan · Accepted Answer · 2013-01-14 16:49:47Z

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.

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.

mishadoff · Accepted Answer · 2013-01-14 16:42:08Z

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

kosa · Accepted Answer · 2013-01-14 16:37:47Z

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, 2013 at 16:37

kosa

66.7k15 gold badges134 silver badges170 bronze badges

1 Comment

Paul Bellora Over a year ago

The page on generic methods would probably be more appropriate.

PermGenError · Accepted Answer · 2013-01-14 16:38:43Z

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

Collectives™ on Stack Overflow

Collections.sort implementation

5 Answers 5

3 Comments

1 Comment

Comments

1 Comment

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

3 Comments

1 Comment

Comments

1 Comment

Comments

Linked

Related