# Quick Sort

http://me.dt.in.th/page/Quicksort/

1. Pick pivot - this is called partitioning
2. Sort to either side of the pivot
3. Quick sort the two sub arrays
• worst case O(n2)
• best/average case O(n log n) - if you pick a random pivot

can be close to O(n) if using parallel version

There are O(log n) levels (the technical way to say that is, “the height of the call stack is O(log n)”).

## Java

``````import java.util.Arrays;
import java.util.List;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class Quicksort {
public static void main(String[] args) {
System.out.println(quicksort(Arrays.asList(10, 5, 2, 3))); // [2, 3, 5, 10]
}

private static List<Integer> quicksort(List<Integer> list) {
if (list.size() < 2) {
// base case, arrays with 0 or 1 element are already "sorted"
return list;
} else {
// recursive case
Integer pivot = list.get(0);

// sub-array of all the elements less than the pivot
List<Integer> less = list.stream().skip(1).filter(el -> el <= pivot)
.collect(Collectors.toList());

// sub-array of all the elements greater than the pivot
List<Integer> greater = list.stream().skip(1).filter(el -> el > pivot)
.collect(Collectors.toList());

return Stream.of(
quicksort(less).stream(),
Stream.of(pivot),
quicksort(greater).stream())
.flatMap(Function.identity()).collect(Collectors.toList());
}
}
}``````