クイックソート(JAVA実装)

アルゴリズムの説明:
ソートする配列をA[0]......A[N-1]とし、まず任意に1つのデータ(通常は配列の最初の数)をキーデータとして選択し、それより小さい数をすべて前に置き、それより大きい数をすべて後ろに置くプロセスを高速ソートと呼ぶ.なお、高速ソートは安定したソートアルゴリズムではなく、すなわち、複数の同じ値の相対位置がアルゴリズムの終了時に変動する可能性がある.1回の高速ソートのアルゴリズムは、次のとおりです.
1)2つの変数i,jを設定し,ソート開始時:i=0,j=N-1;
2)キーデータとして最初の配列要素を用いてkey,すなわちkey=A[0];
3)jから前方探索を開始し、すなわち後から前方探索を開始し(j--)、keyより小さい最初の値A[j]を見つけ、A[j]とA[i]を交換する.
4)iから後方探索を開始し、すなわち前から後方探索(i++)を開始し、keyより大きい最初のA[i]を見つけ、A[i]とA[j]を交換する.
5)i=jになるまで3、4のステップを繰り返す.(3,4ステップでは、条件に合致する値が見つからなかった.すなわち、3中のA[j]がkeyより小さくなく、4中のA[i]がkeyより大きくないときはj,iの値を変更し、j=j-1,i=i+1となるようにする.条件に合致する値を見つけ、交換するときはi,jポインタの位置は変わらない.また、i=jというプロセスは、必ずi+またはj-が完了したときであり、このときループを終了させる).
コード実装:

public class QuickSort {
    public static int sort(int[] array, int low, int high) {
        int key = array[low];
        while (high > low) {
            while (high > low && array[high] >= key) {
                high--;
            }
            array[low] = array[high];
            while (high > low && array[low] <= key) {
                low++;
            }
            array[high] = array[low];
        }
        array[low] = key;
        return low;
    }

    public static void findMiddle(int[] array, int low, int high) {
        if (low >= high) {
            return;
        }
        int middle = sort(array, low, high);
        findMiddle(array, low, middle - 1);
        findMiddle(array, middle + 1, high);
    }


    public static void main(String[] args) {
        int[] array = {-5, 9, 78, -8, 0, 56, -2, -5, 777, 6, 21, 78, -1, 0, -456, -8};
        findMiddle(array, 0, array.length - 1);
        for (int num : array) {
            System.out.print(num + " ");
        }
    }

}

アルゴリズム解析:
最悪の場合:ソートアルゴリズムの最悪の実行時間はθ(n 2)、最悪の場合、分割プロセスによって生成される2つの区間がそれぞれn−1要素と1要素を含む場合に発生する.
最良の場合:分割プロセスごとに発生する区間サイズがn/2の場合、高速ソート法の実行はずっと速くなります.このとき、T(n)=2 T(n/2)+θ(n),T(1)=θ(1)(3)T(n)=θ(nlogn).
≪平均｜Average｜oem_src≫:高速ソートの平均実行時間は次のとおりです.θ(nlogn).