package net.kullo.javautils;

import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Quicksort {
    private Quicksort() {}

    public static <G> void sort(List<G> list, Comparator<G> comparator) {
        sort(list, comparator, 0, list.size() - 1);
    }

    public static <G> void sort(List<G> list, Comparator<G> comparator, int left, int right) {
        if (left < right) {
            int separator = separate(list, comparator, left, right);
            sort(list, comparator, left, separator - 1);
            sort(list, comparator, separator + 1, right);
        }
    }

    public static <G> int separate(List<G> list, Comparator<G> comparator, int left, int right) {
        int i = left;
        int j = right;
        G pivot = list.get(right);

        do {
            while (comparator.compare(list.get(i), pivot) <= 0 && i < right) {
                i++;
            }

            while (comparator.compare(list.get(j), pivot) >= 0 && j > left) {
                j--;
            }

            if (i < j) {
                Collections.swap(list, i, j);
            }
        } while (i < j);

        if (comparator.compare(list.get(i), pivot) > 0) {
            Collections.swap(list, i, right);
        }

        return i;
    }
}

@@ -131,16 +131,612 @@
 ksort %7B%0A
+    public interface PivotStrategy %7B%0A        %3CG%3E void apply(List%3CG%3E list, int left, int right);%0A    %7D%0A%0A    static public class TrivialPivotStrategy implements PivotStrategy %7B%0A        @Override%0A        public %3CG%3E void apply(List%3CG%3E list, int left, int right) %7B%0A            // do nothing%0A        %7D%0A    %7D%0A%0A    static public class MiddleElementPivotStrategy implements PivotStrategy %7B%0A        @Override%0A        public %3CG%3E void apply(List%3CG%3E list, int left, int right) %7B%0A            int pivotPosition = left + (right-left)/2;%0A            Collections.swap(list, pivotPosition, right);%0A        %7D%0A    %7D%0A%0A
     priv
@@ -1003,32 +1003,160 @@
 left %3C right) %7B%0A
+            PivotStrategy pivotStrategy = new MiddleElementPivotStrategy();%0A            pivotStrategy.apply(list, left, right);%0A
             int 

Add a Quicksort pivot strategy