Sorting In Java

Sorting is a very common operation, and Java provides different inbuilt methods which can be used for sorting different data structures. This tutorial will explain how to sort arrays, collections, and user-defined class instances in Java.

Sorting Arrays in Java

An array is a simple data structure that is used to store similar types of data in an ordered way. The sort() method of the Arrays class can be used to sort an entire array or a part of an array. Internally, this method uses a dual-pivot Quicksort Algorithm for sorting primitive data types. For an array of objects, it uses the Merge Sort Algorithm.

public static void main(String[] args)
{
    int[] arrToSort = {7, 9, 1, 0, 2, 5, 6, 11};
    System.out.println("Array Before Sorting: " + Arrays.toString(arrToSort));
    Arrays.sort(arrToSort);
    System.out.println("Array After Sorting: " + Arrays.toString(arrToSort));
}
		

Array Before Sorting: [7, 9, 1, 0, 2, 5, 6, 11]
Array After Sorting: [0, 1, 2, 5, 6, 7, 9, 11]

We can pass a start index and an end index to the Arrays.sort() method to sort just a part of the array. The range defined by the indices is exclusive(the end index element is not included).

public static void main(String[] args)
{
    //Sorting the left half of an Array
	int[] arrToSort = {7, 9, 1, 0, 2, 6, 11, 5, -1, 20};
	System.out.println("Array Before Sorting: " + Arrays.toString(arrToSort));
	int from = 0;
	int to = arrToSort.length / 2;
	Arrays.sort(arrToSort, from, to);
	System.out.println("Array After Sorting: " + Arrays.toString(arrToSort));
}
		

Array Before Sorting: [7, 9, 1, 0, 2, 6, 11, 5, -1, 20]
Array After Sorting: [0, 1, 2, 7, 9, 6, 11, 5, -1, 20]

Java 8 has a new parallelSort() method that uses multithreading to sort different parts of the array simultaneously. This method first divides the array into smaller arrays, and then different threads work on these smaller arrays to sort them parallelly. Then they are merged back into a single sorted array. Just like the Arrays.sort() method, we can use parallelSort() to sort a part of the array.

public static void main(String[] args)
{
    //Sorting using parallel sort
	int[] arrToSort = {7, 9, 1, 0, 2, 5, 6, 11};
	System.out.println("Array Before Sorting: " + Arrays.toString(arrToSort));
	Arrays.parallelSort(arrToSort);
	System.out.println("Array After Sorting: " + Arrays.toString(arrToSort));
}
		

Array Before Sorting: [7, 9, 1, 0, 2, 5, 6, 11]
Array After Sorting: [0, 1, 2, 5, 6, 7, 9, 11]

Sorting Collections in Java

The Collections framework in Java provides multiple data structures to store and manipulate data. Lists, Sets, and Maps are the most frequently used collections. In this section, we will learn how to sort these collections.

Sorting Lists

The Collections framework provides a Collections.sort() method to sort Lists. This method can also take a Comparator as a parameter and sorts the list accordingly.

public static void main(String[] args)
{
    //Sorting Lists
	List<Integer> listToSort = new ArrayList<Integer>();
	listToSort.add(7);
	listToSort.add(9);
	listToSort.add(0);
	listToSort.add(1);
	listToSort.add(-1);
	System.out.println("List Before Sorting: " + listToSort);
		
	Collections.sort(listToSort);
	System.out.println("List After Sorting: " + listToSort);
}
		

List Before Sorting: [7, 9, 0, 1, -1]
List After Sorting: [-1, 0, 1, 7, 9]

We can use the Collections.reverseOrder() method to sort the list in descending order. This method returns a Comparator object which we can pass to the Collections.sort() method.

public static void main(String[] args)
{
    //Sorting lists in reverse order
	List<Integer> listToSort = new ArrayList<Integer>();
	listToSort.add(7);
	listToSort.add(9);
	listToSort.add(0);
	listToSort.add(1);
	listToSort.add(-1);
	System.out.println("List Before Sorting: " + listToSort);
		
	Collections.sort(listToSort, Collections.reverseOrder());
	System.out.println("List After Sorting in descending order: " + listToSort);
}
		

List Before Sorting: [7, 9, 0, 1, -1]
List After Sorting in descending order: [9, 7, 1, 0, -1]

Sorting Sets

Sets are used to store unordered data without any duplicates. Unlike Lists, we don't have a sort() method defined for sets. The HashSet class doesn't maintain insertion order, so we cannot sort it directly. But we can view the sorted values by transferring all elements of the HashSet to a List and then sorting the List.

public static void main(String[] args)
{
    //Sorting Sets using lists
	HashSet<Integer> setToSort = new HashSet<Integer>();
	setToSort.add(7);
	setToSort.add(9);
	setToSort.add(0);
	setToSort.add(1);
	setToSort.add(-1);
	System.out.println("Set Before Sorting: " + setToSort);
		
	ArrayList<Integer> listOfSet = new ArrayList<Integer>(setToSort);
	Collections.sort(listOfSet);
	System.out.println("Sorted Values of the Set: " + listOfSet);
}
		

Set Before Sorting: [0, -1, 1, 7, 9]
Sorted Values of the Set: [-1, 0, 1, 7, 9]

The same approach can be used for LinkedHashSet. The LinkedHashSet maintains the insertion order of elements, and sorted values can be stored back into it.

public static void main(String[] args)
{
	//Sorting Sets using lists
	LinkedHashSet<Integer> setToSort = new LinkedHashSet<Integer>();
	setToSort.add(7);
	setToSort.add(9);
	setToSort.add(0);
	setToSort.add(1);
	setToSort.add(-1);
	System.out.println("Set Before Sorting: " + setToSort);
		
	ArrayList<Integer> listOfSet = new ArrayList<Integer>(setToSort);
	Collections.sort(listOfSet);
		
	//Transferring sorted values to the set
	setToSort = new LinkedHashSet<Integer>(); 
	for(Integer i : listOfSet)
	{
		setToSort.add(i);
	}
		
	System.out.println("Set After Sorting: " + setToSort);
}
		

Set Before Sorting: [7, 9, 0, 1, -1]
Set After Sorting: [-1, 0, 1, 7, 9]

The TreeSet stores the elements in sorted order. So we can convert a HashSet or LinkedHashSet to a TreeSet and view the sorted values.

public static void main(String[] args)
{
	//Sorting Sets using TreeSets
	HashSet<Integer> setToSort = new HashSet<Integer>();
	setToSort.add(7);
	setToSort.add(9);
	setToSort.add(0);
	setToSort.add(1);
	setToSort.add(-1);
	System.out.println("Set Before Sorting: " + setToSort);
		
	TreeSet<Integer> sortedSet = new TreeSet<Integer>(setToSort);
	System.out.println("Set After Sorting: " + sortedSet);
}
		

Set Before Sorting: [0, -1, 1, 7, 9]
Set After Sorting: [-1, 0, 1, 7, 9]

Sorting Maps

Maps are used to store a series of key-value pairs. Just like Sets, we don't have any inbuilt sort() method for Maps. We can sort Maps based on the keys or the values. Let's learn how to sort Maps by key and values.

Sorting Maps By Keys

HashMaps, like HashSets, do not maintain insertion order. We can still view the sorted data with the help of Lists. We will transfer the keys of the HashMap to an ArrayList, and then we will sort this List. We can get the values for the sorted keys by using the get() method of Maps.

public static void main(String[] args)
{
	//Sorting Map by Keys using Lists
	HashMap<Integer, String> mapToSort = new HashMap<Integer, String>();
	mapToSort.put(3, "Jessica");
	mapToSort.put(112, "Victor");
	mapToSort.put(15, "Harry");
	mapToSort.put(104, "Simon");
	mapToSort.put(21, "Justin");
	System.out.println("Map before sorting: ");
	for(Map.Entry<Integer, String> e : mapToSort.entrySet())
		System.out.println(e.getKey() + " " + e.getValue());
		
	ArrayList<Integer> sortedKeys = new ArrayList<Integer>(mapToSort.keySet());
	Collections.sort(sortedKeys);
		
	System.out.println("\nMap After sorting: ");
	for(Integer i : sortedKeys)
		System.out.println(i + " " + mapToSort.get(i));
}
		

Map before sorting:
112 Victor
3 Jessica
21 Justin
104 Simon
15 Harry

Map After sorting:
3 Jessica
15 Harry
21 Justin
104 Simon
112 Victor

We can also create a new LinkedHashMap and add the sorted keys and corresponding values to it. A LinkedHashMap maintains insertion order.

public static void main(String[] args)
{
	HashMap<Integer, String> mapToSort = new HashMap<Integer, String>();
	mapToSort.put(3, "Jessica");
	mapToSort.put(112, "Victor");
	mapToSort.put(15, "Harry");
	mapToSort.put(104, "Simon");
	mapToSort.put(21, "Justin");
	System.out.println("Map before sorting: ");
	for(Map.Entry<Integer, String> e : mapToSort.entrySet())
		System.out.println(e.getKey() + " " + e.getValue());
		
	ArrayList<Integer> sortedKeys = new ArrayList<Integer>(mapToSort.keySet());
	Collections.sort(sortedKeys);
		
	//Creating a new LinkedHashMap
	LinkedHashMap<Integer, String> sortedMap = new LinkedHashMap<Integer, String>();
	for(Integer i : sortedKeys)
		sortedMap.put(i, mapToSort.get(i));
		
	System.out.println("\nThe Sorted Map is:");
	for(Map.Entry<Integer, String> e : sortedMap.entrySet())
		System.out.println(e.getKey() + " " + e.getValue());
}
		

Map before sorting:
112 Victor
3 Jessica
21 Justin
104 Simon
15 Harry

The Sorted Map is:
3 Jessica
15 Harry
21 Justin
104 Simon
112 Victor

Another easy way of sorting a Map by keys is to use a TreeMap. A TreeMap, by default, stores the key-value pairs in sorted order.

public static void main(String[] args)
{
	//Sorting Map by Keys using TreeMap
	HashMap<Integer, String> mapToSort = new HashMap<Integer, String>();
	mapToSort.put(3, "Jessica");
	mapToSort.put(112, "Victor");
	mapToSort.put(15, "Harry");
	mapToSort.put(104, "Simon");
	mapToSort.put(21, "Justin");
		
	System.out.println("Map before sorting: ");
	for(Map.Entry<Integer, String> e : mapToSort.entrySet())
		System.out.println(e.getKey() + " " + e.getValue());
		
	TreeMap<Integer, String> sortedMap = new TreeMap<Integer, String>();
	sortedMap.putAll(mapToSort);

	System.out.println("\nSorted TreeMap: ");
	for(Map.Entry<Integer, String> e : sortedMap.entrySet())
		System.out.println(e.getKey() + " " + e.getValue());
}
		

Map before sorting:
112 Victor
3 Jessica
21 Justin
104 Simon
15 Harry

Sorted TreeMap:
3 Jessica
15 Harry
21 Justin
104 Simon
112 Victor

Sorting Maps By Values

Sorting a Map according to the values is slightly difficult. We will create a class that implements the Comparator interface. Next, we will define a compare() method in it. The code for this class is shown below.

class CompareMapValue implements Comparator<Map.Entry<Integer, String>>
{
	@Override
	public int compare(Entry<Integer, String> o1, Entry<Integer, String> o2)
	{
		String val1 = o1.getValue();
		String val2 = o2.getValue();
		return val1.compareTo(val2);
	}
}

Next, we will create an ArrayList with all the key-value pairs and sort them using the Collections.sort() method. We will pass an object of our previously defined class to the sort() method. We can also use a LinkedHashMap to store the sorted values. In our code, we have just printed the sorted values.

public static void main(String[] args)
{
	
	//Sorting map by values
	HashMap<Integer, String> mapToSort = new HashMap<Integer, String>();
	mapToSort.put(3, "Jessica");
	mapToSort.put(112, "Victor");
	mapToSort.put(15, "Harry");
	mapToSort.put(104, "Simon");
	mapToSort.put(21, "Justin");
		
	System.out.println("Map before sorting: ");
	for(Map.Entry<Integer, String> e : mapToSort.entrySet())
		System.out.println(e.getKey() + " " + e.getValue());
		
	ArrayList<Map.Entry<Integer, String>> list = new ArrayList<>(mapToSort.entrySet());
	CompareMapValue c = new CompareMapValue();
	Collections.sort(list, c);
		
	System.out.println("\nSorted Values: ");
	for (Map.Entry<Integer, String> e : list)
	{
		System.out.println(e.getKey() + " " + e.getValue());
	}
}

Map before sorting:
112 Victor
3 Jessica
21 Justin
104 Simon
15 Harry

Sorted Values:
15 Harry
3 Jessica
21 Justin
104 Simon
112 Victor

Sorting User-Defined Class Objects

We can sort user-defined class objects by using the Comparable and the Comparator interfaces. Refer to our article on Comparators and Comparables to learn how to use them.

To use Comparators, we need to create a separate class, but Java 8 provides us Lambda expressions that can be used to implement Comparators more efficiently. Suppose we need to sort an array of integers in reverse order. We can create a class that implements the Comparator interface and overrides the compare() method, as shown below.

class CompareReverse implements Comparator<Integer>
{
	@Override
	public int compare(Integer o1, Integer o2) {
		return -o1.compareTo(o2);
	}
}

Or we can write the following Lambda expression that does the same thing.

Comparator<Integer> c = (x, y) -> -(Integer.compare(x, y));

The output given by both of them is the same.

public static void main(String[] args)
{
	Integer[] arr = {4, 9, 1, -1, 0, 5};
	List<Integer> arrList1 = Arrays.asList(arr);
	List<Integer> arrList2 = Arrays.asList(arr);
		
	CompareReverse c1 = new CompareReverse();
	Comparator<Integer> c2 = (x, y) -> -(Integer.compare(x, y));
		
	Collections.sort(arrList1, c1);
	Collections.sort(arrList2, c2);
		
	System.out.println(arrList1);
	System.out.println(arrList2);
}

[9, 5, 4, 1, 0, -1]
[9, 5, 4, 1, 0, -1]

Using comparing() and thenComparing() methods

The comparing() and thenComparing() methods are also a great way of using Comparators to sort user-defined class instances. Consider a Student class with name and GPA as attributes.

class Student
{
	String name;
	Double gpa;
	
	Student(String name, Double gpa)
	{
		this.name = name;
		this.gpa = gpa;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	public Double getGpa() {
		return gpa;
	}

	public void setGpa(Double gpa) {
		this.gpa = gpa;
	}
}

If we wish to sort an array of students by their GPA, then we can use the comparing() method, as shown below.

public static void main(String[] args)
{
	ArrayList<Student> listOfStudents = new ArrayList<Student>();
	listOfStudents.add(new Student("Rachel", 8.08));
	listOfStudents.add(new Student("Justin", 8.08));
	listOfStudents.add(new Student("Clay", 9.75));
	listOfStudents.add(new Student("Austin", 9.75));
	listOfStudents.add(new Student("Chloe", 9.33));
	Comparator<Student> c = Comparator.comparing(Student :: getGpa);
		
	Collections.sort(listOfStudents, c);
		
	for(Student s : listOfStudents)
		System.out.println(s.getName() + " " + s.getGpa());
}

Rachel 8.08
Justin 8.08
Chloe 9.33
Clay 9.75
Austin 9.75

Let's sort the above array first by student name and then by student's GPA. We can use the thenComparing() method with the comparing() method to do this. The code for this scenario is shown below. Make sure to define appropriate getters to use with these methods.

public static void main(String[] args)
{
	ArrayList<Student> listOfStudents = new ArrayList<Student>();
	listOfStudents.add(new Student("Rachel", 8.08));
	listOfStudents.add(new Student("Justin", 8.08));
	listOfStudents.add(new Student("Clay", 9.75));
	listOfStudents.add(new Student("Austin", 9.75));
	listOfStudents.add(new Student("Chloe", 9.33));
	Comparator<Student> c = Comparator.comparing(Student :: getGpa).thenComparing(Student :: getName);
		
	Collections.sort(listOfStudents, c);
		
	for(Student s : listOfStudents)
		System.out.println(s.getName() + " " + s.getGpa());
}

Justin 8.08
Rachel 8.08
Chloe 9.33
Austin 9.75
Clay 9.75

Summary

This tutorial explains how to sort different data structures like arrays, lists, sets, and maps in Java. Arrays can be sorted by using the Arrays.sort() method. If we have an array of larger sizes, then it is recommended to use parallelSort(), as it is much more efficient than the normal sort() method. The Collections framework provides a sort() method for the List interface. We can also sort Sets and Maps by using Lists. A TreeSet can also be used to store values in sorted order. Similarly, the TreeMap can also be used to sort maps.