Saturday 26 September 2015

Secret of Collections.sort()

How java.util.Collections.sort(List<T> list) works ?

Preface : 
  • All implementation class of List interface overrides toArray() method which returns an array of elements of that list. Except LinkedList all other list holds elements as a form of array internally. Only LinkedList holds in form of linked nodes (not in array form). 
  • List.toArray()
    • LinkedList iterates the linked nodes and store each node into a new array and returns the same
    • Other List implementation classes return a copy of the array that holds the element
  • Collections.sort():
    • sorts the array using Arrays.sort(Object[] a) which uses merge sort algorithm internally to sort the supplied array
    • then using ListIterator of the supplied list, it updates the elements from the sorted array

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    Object[] a = list.toArray(); // Gets array here
    Arrays.sort(a); // Sorting array here
    ListIterator<T> i = list.listIterator();
    for (int j=0; j<a.length; j++) {
        i.next();
        i.set((T)a[j]);  // Updating list here
    }
}
Similarly it uses Arrays.sort(T[] a, Comparator<? super T> c) method when comparator is supplied

No comments:

Post a Comment