import java.util.ArrayList;
import java.util.List;

public class QuickSort1 {
	public static void main(String[] args) {
		List<Integer> years = List.of(
			1492,
			1776,
			1066,
			1812,
			1984,
			2001,
			476,
			2019,
			1945
		);

		List<Integer> sortedYears = quickSort(years); 

		for (int year: sortedYears) {
			System.out.println(year);
		}

		System.exit(0);
	}

	//Create and return a new List containing the ints in ascending order.

	private static List<Integer> quickSort(List<Integer> list) {
		if (list.size() <= 1) {
			return list;  //No sorting needed: the list is already in order.
		}

		int pivot = list.get(list.size() / 2);   //the int in the middle

		//Create three shorter Lists.
		List<Integer> smallValues  = new ArrayList<Integer>();
		List<Integer> mediumValues = new ArrayList<Integer>();
		List<Integer> bigValues    = new ArrayList<Integer>();

		for (int i: list) {
			if (i < pivot) {   //also try java.lang.Integer.signum
				smallValues.add(i);
			} else if (i == pivot) {
				mediumValues.add(i);
			} else {
				bigValues.add(i);
			}
		}

		//Concatenate the three shorter Lists.
		List<Integer> concatenation = new ArrayList<Integer>();
		concatenation.addAll(quickSort(smallValues));
		concatenation.addAll(mediumValues);
		concatenation.addAll(quickSort(bigValues));
		return concatenation;
	}

}