今回はマージソートです。

マージソートの処理は

1.ソートするリストを2つに分ける
2.分けたリストをソートする
3.2つのリストをマージする

の3つの処理を再帰的に行うことでソートします。

1. のソートするリストの要素が0か1の場合にはソートする必要が無いのでリストをそのまま返します。これにより処理2で無限再帰しないことが保障されます。

2. の分けたリストをソートする部分でマージソートを再帰呼び出しします。

3. のマージでは2つのリストのそれぞれの先頭の値を比較し小さい(または大きい)方の値を取り出して結果のリストに追加します。

sort/MergeSort.java

package sort;

import java.util.List; import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Collections;

public class MergeSort {
  private static <E extends Comparable<E>> List<E> merge(List<E> lhs, List<E> rhs) {
    List<E> list = new LinkedList<E>();
    int lidx = 0, ridx = 0;
    while (true) {
      if (lidx >= lhs.size()) {
        list.addAll(rhs.subList(ridx, rhs.size()));
        return list;
      }
      if (ridx >= rhs.size()) {
        list.addAll(lhs.subList(lidx, lhs.size()));
        return list;
      }
      E l = lhs.get(lidx);
      E r = rhs.get(ridx);
      if (l.compareTo(r) < 0) {
        list.add(l);
        lidx++;
      } else {
        list.add(r);
        ridx++;
      }
    }
  }
  public static <E extends Comparable<E>> List<E> sort(List<E> list) {
    if (list.size() < 2) {
      return list;
    }
    List<E> lhs = list.subList(0, list.size()/2);
    List<E> rhs = list.subList(list.size()/2, list.size());
    return merge(sort(lhs), sort(rhs));
  }
  public static void main(String args[]) {
    List<Integer> list = new ArrayList<Integer>();
    for (int i = 0; i < 10; i++) {
      list.add(i);
    }
    Collections.shuffle(list);
    System.out.println(list);
    list = sort(list); 
    System.out.println(list);
  }
}