import java.util.stream.*;
import java.util.*;

/*
  An attempt to implement quickSort using Java 8 as close as possible to
  the elegant Haskell implementation:

  quicksort [] = []
  quicksort (x:xs) =
    let smallerSorted = quicksort [a | a <- xs, a <= x]
        biggerSorted = quicksort [a | a <- xs, a > x]
    in  smallerSorted ++ [x] ++ biggerSorted

*/


public class QuickSort{

  public static List<Integer> quickSort(List<Integer> xs){

    if(xs.size() <= 1){
      return xs;
    }

    int x = xs.get(0); //choosing the first element as the pivot

    //smallerSorted = quicksort [a | a <- xs, a <= x]
    List<Integer> smallerSorted = quickSort(
                                    xs.stream()
                                      .skip(1) //removing pivot
                                      .filter(i -> i <= x) //filter the elements <= x
                                      .collect(Collectors.toList())); //convert the stream back to List

    //biggerSorted = quicksort [a | a <- xs, a > x]
    List<Integer> biggerSorted = quickSort(
                                    xs.stream()
                                      .skip(1) //removing pivot
                                      .filter(i -> i > x) //filter the elements > x
                                      .collect(Collectors.toList())); //convert the stream back to List

    //smallerSorted ++ [x] ++ biggerSorted 
    return Stream.concat(Stream.concat(smallerSorted.stream(),Stream.of(x)),biggerSorted.stream())
           .collect(Collectors.toList());
  }

  public static void main(String[] args) {
    System.out.println(QuickSort.quickSort(new ArrayList<Integer>(Arrays.asList(3,1,2,4,5,3,4,6,7,4,6)))); //[1, 2, 3, 3, 4, 4, 4, 5, 6, 6, 7]
  }
}