今回はシアソート (またはシェアソート) です。このアルゴリズムはリストを2次元テーブルに見立てて、行と列ごとに繰り返しソートすることで最終的にはリスト全体がソートされるというアルゴリズムです。各行、各列をソートするときのアルゴリズムは任意です。

このアルゴリズムのメリットは列ごとにソートを行うときに各行または各列ごとに独立して並列にソートすることができるので適切に実装を行えばマルチプロセッサ環境で高速にソートできることです。

下記はJavaによる実装です。

sort/ShearSort.java

package sort;

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

public class ShareSort {

  rivate static class ShearColList<E> extends AbstractList<E> {
    private final List<E> SRC;
    private final int COL;
    private final int SHEAR;

    public ShearColList(List<E> src, int shear, int col) {
      this.SRC = src;
      this.COL = col;
      this.SHEAR = shear;
    }

    private int srcIndex(int index) {
      int off = isEven(index) ? COL : SHEAR - COL - 1;
      return index * SHEAR + off;
    }

    @Override
    public E get(int index) {
      return SRC.get(srcIndex(index));
    }

    public E set(int index, E element) {
      return SRC.set(srcIndex(index), element);
    };

    @Override
    public int size() {
      boolean ext = srcIndex(SRC.size() / SHEAR) < SRC.size();
      return (SRC.size() / SHEAR) + (ext ? 1 : 0);
    }

  }

  private static boolean isEven(int n) {
    return (n % 2) == 0;
  }

  public static<E extends Comparable<E>> List<E> sort(List<E> list) {
    int shear = (int) Math.sqrt(list.size());
    int log2 = 1;
    for (int a = shear; a != 0; a /= 2, log2++) ;
    for (int i = 0; i < log2; i++) {
      for (int off = 0; off < list.size(); off += shear) {
        Collections.sort(list.subList(off, Math.min(off + shear, list.size())));
      }
      for (int j = 0; j < shear; j++) {
        Collections.sort(new ShearColList<E>(list, shear, j));
      }
    }
    return list;
  }

  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);
    System.out.println(sort(list));
  }
}