Java で、クイックソート（Quick Sort）を実装する。

ソートのアルゴリズムの中でも最も速いとされているのがクイックソートだ。平均計算量は O(n log n) とされている。しかし最悪のケースの場合は O(n^2) である。このアルゴリズムは、

データを半分に分ける。例 9452353381 の並びのデータの場合、94523 5 3381 というように、真ん中へんの 5 でデータを左右にわける。
分けた場所にあった1つのデータ（上の例では 5、下のコードでは middle という名前の変数）と、左右に分けたデータの大小をを1つずつ比べる。比較したデータが大きかったらそのデータより右の方へ、小さかったら左の方へと振り分ける（分割という）。このときに、左に振り分けたデータ、右に振り分けたデータの並びはなんでもいい。とにかく真ん中の値と比べて、ひたすら左右に振り分けるのである。
左右に振り分けるのだから当然その入れ物が必要になる。下のコードでは
List<integer> left = new ArrayList<integer>(); List<integer> right = new ArrayList<integer>();
としているところがそう。いわゆるキュー（として ArrayList）を用意している。
左右に振り分けたデータを、1. に戻ってさらにまた半分に分けて同じことを繰り返す。
同じことを繰り返すということは、データをどんどん半分半分にしていくということだから、最後は 2か3つのデータしか残らなくなる。そうなったら比較するものがなくなったので分割していったデータを組み立てていく。なぜなら、分割した最小単位のデータはすでにソートされているし、左右に振り分けていたのだから最初に半分に分けたデータよりも大きいか小さいかのデータの塊となっているからだ。

import java.util.*;

public class Sort {

  private Sort() {
  }

  public static void output(List<Integer> data) {
    for(int i = 0, n = data.size(); i < n; i++)
System.out.print(data.get(i) + ", ");
System.out.println();
  }

  public static List<Integer> quicksort(List<Integer> data) {

    if(data.size() < 1) return new ArrayList<Integer>();
    Integer middle = data.get(data.size() / 2);
    List<Integer> left   = new ArrayList<Integer>();
    List<Integer> right  = new ArrayList<Integer>();
    for(int i = 0, n = data.size(); i < n; i++) {
      // pass through the pivot data: data[data.size() / 2]
      if(i != data.size() / 2) {
        if(data.get(i) <= middle) {  // leftward, rightward spreading
          left.add(data.get(i));
        } else {
          right.add(data.get(i));
        }
      }
    }

    List<Integer> result = new ArrayList<Integer>();
    result.addAll(quicksort(left));
    result.add(middle);
    result.addAll(quicksort(right));
    output(result);

    return result;
  }

  public static void main( String[] args ) {

    List<Integer> data = new ArrayList<Integer>();

    data.add(9); // 0
    data.add(4); // 1
    data.add(5); // 2
    data.add(2); // 3
    data.add(3); // 4
    data.add(5); // 5
    data.add(3); // 6
    data.add(3); // 7
    data.add(8); // 8
    data.add(1); // 9

    Sort.output(Sort.quicksort(data));
  }
}