Introduction:

In this tutorial, we’ll learn how to sort arrays as well as collections like List, Set, and Map using Java API.

Sorting Arrays:

Java exposes java.util.Arrays.sort() API which helps us to sort our arrays. There are two flavors to it:

public static void sort(type[] arr)

//sorts array in range [fromIndex - toIndex) : toIndex exclusive 
public static void sort(type[] arr, int fromIndex, int toIndex)

Let’s look at some examples:

int[] arr1 = new int[] {9, 5, 6, 3, 1, 2};
Arrays.sort(arr1);
System.out.println(Arrays.toString(arr1)); //prints [1, 2, 3, 5, 6, 9]

int[] arr2 = new int[] {4, 6, 1, 8, 3, 7};
Arrays.sort(arr2, 1, 4);
System.out.println(Arrays.toString(arr2)); //prints [4, 1, 6, 8, 3, 7]

 

Clearly, Arrays.sort(array, fromIndex, toIndex) sorts the array in the index range of fromIndex to toIndex (toIndex exclusive).

 

As mentioned in the Javadoc, Arrays.sort() internally uses quick-sort dual-pivot implementation when sorting primitives. It, however, uses a flavor of merge-sort when working with an array of objects.

Sorting Members Of Collection API:

1. List<T> :
   

   java.util.Collections.sort() is the method that helps us sort a List:

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

   So, using it is pretty simple:

   List<Integer> list = new ArrayList<>();
   list.add(13);
   list.add(8);
   list.add(10);
   
   Collections.sort(list);
   
   System.out.println(list); // prints [8, 10, 13]

   Collections.sort() method internally makes use of a modified merge-sort implementation and offers O(nlogn) performance.

2. Set<T> :

   On looking at the definition of Collections.sort() method a little more carefully, we’ll realize that it only accepts a parameter of type List. So what if we want a sorted Set?

   For that, we can either choose to use TreeSet which always maintains a sorted Set. If we have a HashSet, we can still create a temporary TreeSet holding all values from our HashSet which will then be sorted automatically.

   Set<Integer> set = new HashSet<>();
   set.add(5); 
   set.add(3); 
   set.add(8); 
   set.add(1);
   
   Set<Integer> sortedSet = new TreeSet<>(set);
   
   System.out.println(sortedSet);

    

   Or else, we’ll have to:

   • Wrap our Set<T> into a List<T>
   • Sort the List<T>
   • Unwrap our Set<T> from the Sorted List<T>

   List<Integer> list = new ArrayList<>(set); //Step-1
   
   Collections.sort(list); //Step-2
   
   Set<Integer> sortedSet = new LinkedHashSet<>(list); // Step-3
   
   System.out.println(sortedSet); //prints [1, 3, 5, 8]
   
   

3. Map<K, V>:

   When trying to sort the items stored in our Map, we would do it either by keys or by values. Let’s look at both the cases:

   • Sorting By Map Keys: A simple way to sort the elements in a Map(say HashMap) based on keys would be to create a TreeMap out of it:

     Map<Integer, String> map = new HashMap<>();
     map.put(4, "D");
     map.put(1, "A");
     map.put(3, "C");
     map.put(2, "B");
     
     Map<Integer, String> sortedMap = new TreeMap<>(map);
     
     System.out.println(sortedMap); //prints {1=A, 2=B, 3=C, 4=D}
     

     Usually, we should choose our Collection wisely to avoid such scenarios, in the first place. However, when dealing with say some third-party APIs we might end up feeling a need for such solutions.

   • Sorting By Map Values: When trying to sort a Map based on values, we’ll have to follow a few steps:
     • Retrieve all entries using entrySet() method which returns a Set instance
     • Convert the Set of entries retrieved to List
     • Sort the List of entries using our custom comparator
     • Retrieve a LinkedHashMap object from the sorted List of entries(Using LinkedHashMap retains the sorted order while copying items)

     Our implementation would look like:

     Map<Integer, String> map = new HashMap<>();
     map.put(4, "A");
     map.put(1, "B");
     map.put(3, "C");
     map.put(2, "D");
     
     Set<Map.Entry<Integer, String>> set = map.entrySet(); //Step-1
     
     List<Map.Entry<Integer, String>> list = new ArrayList<>(set); //Step-2
     
     Collections.sort(list, (o1, o2) -> o1.getValue().compareTo(o2.getValue())); //Step-3
     
     Map<Integer, String> sortedByValueMap = new LinkedHashMap<>();
     for(Map.Entry<Integer, String> entry : list){            //Step-4
         sortedByValueMap.put(entry.getKey(), entry.getValue());
     }
     
     System.out.println(sortedByValueMap); //prints {4=A, 1=B, 3=C, 2=D}
     
     

     We can further clean our code using Java 8 Streams API and write it as:

     Map<Integer, String> sortedMap = map.entrySet()
         .stream().sorted(Comparator.comparing(Map.Entry::getValue))
         .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue
           , (k1, k2) -> k1,  LinkedHashMap::new));
     
     System.out.println(sortedMap); //prints {4=A, 1=B, 3=C, 2=D}

Please note that when having custom objects stored in an array or a list, we need to write our own comparator for object comparison.

Sorting In Reverse Order:

When we wish you sort our array in reverse order/ descending order, we can use below mentioned Comparator to achieve it:

Integer[] arr = new Integer[] {9, 5, 6, 3, 1, 2};
Arrays.sort(arr, Collections.reverseOrder());
System.out.println(Arrays.toString(arr));

Note that we have used Integer array instead of type –int, as doing so will make the code compilation fail. The reason behind it is that the primitives are not expected to have custom comparators.

Similarly, when sorting a Collection in descending order, we can write a similar code:

Collections.sort(list, Collections.reverseOrder());

Conclusion:

We learned how to sort an array or a Collection like List, Set or Map in Java. We looked at sorting a Map both by key as well as values.

We also covered sorting an array or a Collection in descending order.