深入理解Arrays.sort()

Arrays.sort(T[], Comparator < ? super T > c) is a method for sorting user-defined object array. The official Java Doc briefly describe what it does, but not much for deep understanding. In this post, I will walk though the key information for deeper understanding of this method.

How to Use Arrays.sort(): A Simple Example

By reading the following example, you can quickly get an idea of how to use this method correctly. A Comparator is defined for comparing Dogs by size and then the Comparator is used as a parameter for the sort method.

import java.util.Arrays;
import java.util.Comparator;
 
class Dog{
	int size;	
	public Dog(int s){
		size = s;
	}
}
 
class DogSizeComparator implements Comparator<Dog>{
 
	@Override
	public int compare(Dog o1, Dog o2) {
		return o1.size - o2.size;
	}
}
 
public class ArraySort {
 
	public static void main(String[] args) {
		Dog d1 = new Dog(2);
		Dog d2 = new Dog(1);
		Dog d3 = new Dog(3);
 
		Dog[] dogArray = {d1, d2, d3};
		printDogs(dogArray);
 
		Arrays.sort(dogArray, new DogSizeComparator());	
		printDogs(dogArray);
	}
 
	public static void printDogs(Dog[] dogs){
		for(Dog d: dogs)
			System.out.print(d.size + " " );
 
		System.out.println();
	}
}

Output:
​
2 1 3
1 2 3

The Strategy Pattern Used in Arrays.sort()

As this is a perfect example of Strategy pattern, it is worth to mention here why strategy pattern is good for this situation. In brief, Strategy pattern enables different algorithms get selected at run-time. In this case, by passing different Comparator, different algorithms can get selected. Based on the example above and now assuming you have another Comparator which compares Dogs by weight instead of by size, you can simply create a new Comparator like the following.

class Dog{
	int size;
	int weight;
 
	public Dog(int s, int w){
		size = s;
		weight = w; 
	}
}
 
class DogSizeComparator implements Comparator<Dog>{
 
	@Override
	public int compare(Dog o1, Dog o2) {
		return o1.size - o2.size;
	}
}
 
class DogWeightComparator implements Comparator<Dog>{
 
	@Override
	public int compare(Dog o1, Dog o2) {
		return o1.weight - o2.weight;
	}
}
 
public class ArraySort {
	public static void main(String[] args) {
		Dog d1 = new Dog(2, 50);
		Dog d2 = new Dog(1, 30);
		Dog d3 = new Dog(3, 40);
 
		Dog[] dogArray = {d1, d2, d3};
		printDogs(dogArray);
 
		Arrays.sort(dogArray, new DogSizeComparator());	
		printDogs(dogArray);
 
		Arrays.sort(dogArray, new DogWeightComparator());	
		printDogs(dogArray);
	}
 
	public static void printDogs(Dog[] dogs){
		for(Dog d: dogs)
			System.out.print("size="+d.size + " weight=" + d.weight + " ");
 
		System.out.println();
	}
}

Output:

size=2 weight=50 size=1 weight=30 size=3 weight=40 
size=1 weight=30 size=2 weight=50 size=3 weight=40 
size=1 weight=30 size=3 weight=40 size=2 weight=50 

Comparator is just an interface. Any Comparator that implements this interface can be used during run-time. This is the key idea of Strategy design pattern

Why Use “super”?

It is straightforward if Comparator < T > c is the parameter, but the second parameter is Comparator< ? super T > c. < ? super T > means the type can be T or its super types. Why it allows super types? The answer is: This approach allows using same comparator for all sub classes. This is almost obvious in the following example.

import java.util.Arrays;
import java.util.Comparator;
 
class Animal{
	int size;
}
 
class Dog extends Animal{
	public Dog(int s){
		size = s;
	}
}
 
class Cat extends Animal{
	public Cat(int s){
		size  = s;
	}
}
 
class AnimalSizeComparator implements Comparator<Animal>{
 
	@Override
	public int compare(Animal o1, Animal o2) {
		return o1.size - o2.size;
	}
	//in this way, all sub classes of Animal can use this comparator.
}
 
public class ArraySort {
 
	public static void main(String[] args) {
		Dog d1 = new Dog(2);
		Dog d2 = new Dog(1);
		Dog d3 = new Dog(3);
 
		Dog[] dogArray = {d1, d2, d3};
		printDogs(dogArray);
 
		Arrays.sort(dogArray, new AnimalSizeComparator());	
		printDogs(dogArray);
 
		System.out.println();
 
		//when you have an array of Cat, same Comparator can be used. 
		Cat c1 = new Cat(2);
		Cat c2 = new Cat(1);
		Cat c3 = new Cat(3);
 
		Cat[] catArray = {c1, c2, c3};
		printDogs(catArray);
 
		Arrays.sort(catArray, new AnimalSizeComparator());	
		printDogs(catArray);
	}
 
	public static void printDogs(Animal[] animals){
		for(Animal a: animals)
			System.out.print("size="+a.size + " ");
		System.out.println();
	}
}

Outout:

size=2 size=1 size=3 
size=1 size=2 size=3 

size=2 size=1 size=3 
size=1 size=2 size=3 

Summary

To summarize, the takeaway messages from Arrays.sort():

1. genetic-super
2. stratey pattern
3. merge sort-nlog(n) time complexity
4. Java.util.Collections#sort(Listlist,Comparator<? super T>c)has similar idea with Arrays.sort.

Reference:

• Arrays.sort(T[], java.util.Comparator)
• Translation