Collections vs Arrays regarding sort()

Question

Collections vs Arrays regarding sort() What is the difference between these two regarding sort() method? I know Arrays' sort() is using binary search for sort(), what about Collections'? And how to choose which to use? Thanks!

Answer 1

Well, besides operating on different stuff (Collections.sort operates on a List, and Arrays.sort operates on an array), java.util.Collections.sort() simply calls java.util.Arrays.sort() to do the heavy lifting.

Also, for what it's worth, notice that Arrays.sort runs a merge sort.

Answer 2

Collections.sort() Operates on List Whereas Arrays.sort() Operates on an Array.

Arrays.sort() uses Dual-Pivot Quicksort for Primitive Arrays and MergeSort for sorting array of Objects.

Example of Collections.sort() :

 ArrayList<Integer> arr = new ArrayList<Integer>();
 arr.add(15);
 arr.add(10);
 arr.add(5); 
 arr.add(2); 

 Collections.sort(arr);

Example of Arrays.sort() :

int[] arr = new int[4]
 arr[0]=15;
 arr[1]=10;
 arr[2]=5; 
 arr[3]=2; 

 Arrays.sort(arr);

Answer 3

I know Arrays' sort() is using binary search for sort()

No, you don't know any such thing. It doesn't do that. See the Javadoc.

The statement doesn't even make sense. You can't 'use binary search for sort'. Binary search only worked when the data is already sorted. Maybe what you read is that Arrays.binarySearch() assumes the data is sorted.

Answer 4

Use Arrays.sort() if you're dealing with an Array. Use Collections.sort() if you're dealing with something that implements the Collection interface (eg ArrayList).

Answer 5

Collection.sort is used when you dealing with lists and arrays.sort is sued when dealing with arrays. But internally Collection.sort uses Arrays.sort method only. Now internally sorting is done based in Timosrt technique instead of merge sort , because stable, adaptive arrays takes O(nlogn) comparisons in Merge sort but in Timsort worst case it will take O(nlogn) and in worst case storage requies n/2 in Timsort but it is not in the case of Merge sort technique.

Answer 6

As the other answers have said, you would use Collections.sort() when dealing with an object that implements the Collection interface and the Arrays.sort() method when dealing with an Array.

A related question is what type of data structures are better if you want to sort a set of values. If you need to use a List, then I would suggest using a LinkedList since insertions run in O(1) where something like an ArrayList would be O(n).

You could also opt for using a SortedSet if there will be no duplicates or having duplicates is unwanted. That way you don't have to bother with using an external sort method.

Answer 7

Class Arrays

public static void sort(T[] a)

Parameters:
a - the array to be sorted

Implementation note (truncated):

1. Dual-Pivot Quicksort and offers O(n log(n)) performance on many data sets.
2. Faster than traditional (one-pivot) Quicksort implementations.

Class Collections

public static <T extends Comparable<? super T>> void sort(List list)

Parameters:
list - the list to be sorted.

Implementation note (truncated):

1. Is a mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted, while offering the performance of a traditional mergesort when the input array is randomly ordered.
2. If the input array is nearly sorted, the implementation requires approximately n comparisons.
3. Temporary storage requirements vary from a small constant for nearly sorted input arrays to n/2 object references for randomly ordered input arrays.

Summation

1. They are based on different types of data with one in Array and another in List.
2. When concerning the time complexity, it depends on the data is partially sorted or randomly sorted
3. When concerning the space, Arrays.sort requires constant time, but Collections.sort may take up to n/2 space.

Answer 8

Arrays.sort() sorts Arrays i.e. Objects that are in contiguous memory locations. It works on array input.

Collections.sort() can sort objects on both contiguous and discrete memory locations: i.e. it can work on both ArrayList and LinkedList. Collections.sort() internally converts List into Array of objects and calls Arrays.sort() to sort them. It always create extra copy of original list objects. For ArrayList as input, it creates extra copy to maintain mutability of original array. For LinkedList as input, a new array is created for better performance purpose.