private int partition() {
        int center = (start + end) / 2;

        if (array[center] < array[start]) {
            swap(center, start);
        }
        if (array[end] < array[start]) {
            swap(start, end);
        }
        if (array[end] < array[center]) {
            swap(center, end);
        }

        int pivotIndex = center;

        swap(pivotIndex, end - 1);

        int pivot = array[end - 1];
        int left = start;
        int right = end - 1;
        
        while (array[++left] < pivot);
        while (pivot < array[--right]);

        while (left < right) {
            swap(left, right);
            while (array[++left] < pivot);
            while (pivot < array[--right]);
        }

        pivotIndex = left;
        swap(pivotIndex, end - 1);
        return pivotIndex;
    }