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

import java.util.function.Predicate;
import java.util.stream.Collectors;

public class QuickSort2 {
	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.
		var smallValues  = list.stream().filter(i -> i <  pivot).collect(Collectors.toList());
		var mediumValues = list.stream().filter(i -> i == pivot).collect(Collectors.toList());
		var bigValues    = list.stream().filter(i -> i >  pivot).collect(Collectors.toList());

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

}