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