シェアソート（）は、ソートのアルゴリズムの一つ。シェアソートでは、データを長方形に並べた上で、各行／各列ごとにソートを行なう。1989年に Isaac D. Scherson らが発表した。安定ではない内部ソートであり、最悪の場合の時間計算量はO(n1.5)である。各行／各列の比較は互いに独立であるため、バブルソートとは異なり、並列動作が可能である。

 アルゴリズム 
シェアソートの手順は、回の段階に分けられる。

奇数番目の段階(1,3,5,7･･･番目の段階)
行ごとに、奇数行目は左側が小さく、偶数行目は右側が小さくなるようにソートする。
偶数番目の段階(2,4,6,8･･･番目の段階)
列ごとに、上が小さくなるようにソートする。
最後の段階
行ごとに、左側が小さくなるようにソートする。

実装例
/**
 * シェアソート サンプル
 */
public class ShearSort {
 /**
 * 画面表示用:一列いくつで表示するか
 */
 private int col;
 /**
 * ソートする配列
 */
 private int array[];

 /**
 * 動作試験用メインルーチン
 */
 public static void main(String args[]) {
 // ソートしたい配列の長さ
 int arrLen;
 // 引数から配列の長さを取得
 if (args.length == 0) {
 // 省略時は100とする
 arrLen = 100;
 } else {
 arrLen = Integer.parseInt(args);
 // 配列の長さは正の数
 if (arrLen < 1) {
 System.err.println("不正な引数: " + args);
 System.exit;
 }
 }
 // 乱数を初期値として設定
 ShearSort obj = new ShearSort(arrLen);
 // 開始時刻の取得
 long stime = System.currentTimeMillis(); 
 // シェアソート実行
 obj.shearSort();
 // 終了時刻の取得
 long etime = System.currentTimeMillis(); 
 obj.printArray("ソート後 ");
 System.out.println("ShearSort: " + (etime - stime) + "ミリ秒");
 }

 /**
 * @param length 配列の要素数
 */
 private ShearSort(int length) {
 // 配列を確保
 array = new int[length];
 // 乱数を配列に設定
 for (int i = 0; i < length; i++) {
 array[i] = (int)(Math.random() * 1000);
 }
 }

 /**
 * 配列の内容を表示する
 * @param msg 表示するメッセージ
 */
 private void printArray(String msg) {
 System.out.println(msg);
 for(int i = 0; i < array.length; i++) {
 if (i % col == 0) {
 System.out.println();
 }
 System.out.printf(" %5d", array[i]);
 }
 System.out.println();
 }

 /**
 * 奇偶転置ソート
 * 配列の一部を行単位、列単位でソートする。
 * @param start ソート開始位置
 * @param end ソート終了位置
 * @param step ソート間隔
 * @param isinc ソート順序（true：昇順 false：降順）
 */
 private void oeTranSort(int start, int end, int step, boolean isinc) {
 boolean flag = false;
 do {
 flag = false;
 for (int i = start; i + step <= end; i += step * 2) {
 if ((isinc && (array[i] > array[i + step]))
 || (!isinc && (array[i] < array[i + step]))) {
 int temp = array[i];
 array[i] = array[i + step];
 array[i + step] = temp;
 flag = true;
 }
 }
 for (int i = start + step; i + step <= end; i += step * 2) {
 if ((isinc && (array[i] > array[i + step]))
 || (!isinc && (array[i] < array[i + step]))) {
 int temp = array[i];
 array[i] = array[i + step];
 array[i + step] = temp;
 flag = true;
 }
 }
 } while (flag);
 }

 /**
 * シェアソート
 * 配列をソートする。
 */
 private void shearSort() {
 // 配列の長さ
 final int len = array.length;
 // できるだけ大きく正方形に近い長方形ができるように並べる
 // 行数
 int row = (int)Math.sqrt(len);
 // 列数
 col = len / row;
 // 行数*列数で並べた時に余る個数
 int amari = len - row * col;
 if (amari != 0) {
 // 余りがあり行数が3以上の奇数の場合、余りが偶数行目に並ぶので
 // 一行減らして余りが奇数行目に並ぶように行数/列数を変更する
 if ((row % 2 == 1) && (row != 1)) {
 row--;
 col = len / row;
 amari = len - row * col;
 }
 }
 // 2を底とする行数の対数
 // ただし行数が2の累乗ちょうどの場合には、さらに+1する
 int exp = 1;
 // 2を底とする行数の対数
 int log = 0;
 while (exp <= row) {
 exp *= 2;
 log++;
 }
 // 配列の内容を表示
 printArray("ソート前 "); 
 // ソートする範囲の上限
 int max;
 for (int k = 0; k < log; k++) {
 // 行ごとに、奇数行目は左側が小さく、
 // 偶数行目は右側が小さくなるようにソートする
 for (int j = 0; j < row + (amari > 0 ? 1 : 0); j++) {
 // その行の末尾
 max = (j + 1) * col - 1;
 // あまった部分の行には、列数分のデータがない
 if (max >= len) {
 max = len - 1;
 }
 // 当該行をソートする
 oeTranSort(j * col, max, 1, (j % 2) == 0);
 }
 // 列ごとに、上が小さくなるようにソートする。 
 for (int j = 0; j < col; j++) {
 // 余りのある列は、最初に求めた行数よりもデータが一つ多い
 oeTranSort(j, (row - (j < amari ? 0 : 1)) * col + j, 
 col, true);
 }
 } // 規定回数分、行/列のソートを繰り返す
 // 行ごとに、左側が小さくなるようにソートする。 
 for (int j = 0; j < row + (amari > 0 ? 1 : 0); j++) {
 max = (j + 1) * col - 1;
 if (max >= len) {
 max = len - 1;
 }
 oeTranSort(j * col, max, 1, true);
 }
 }
}

動作例
初期データ:
{| rules="all" style="text-align:right"
| 25 || 9 || 5 || 19 || 20 || 6 || 29
|-
| 8 || 24 || 32 || 14 || 34 || 10 || 28
|-
| 26 || 3 || 18 || 2 || 22 || 21 || 11
|-
| 17 || 27 || 15 || 23 || 13 || 35 || 30
|-
| 16 || 33 || 4 || 31 || 7 || 1 || 12
|}

奇数行目は左が小さく、偶数行目は右が小さくなるようにソートする。
{| rules="rows" style="text-align:right"
| 5 || 6 || 9 || 19 || 20 || 25 || 29
|-
| 34 || 32 || 28 || 24 || 14 || 10 || 8
|-
| 2 || 3 || 11 || 18 || 21 || 22 || 26
|-
| 35 || 30 || 27 || 23 || 17 || 15 || 13
|-
| 1 || 4 || 7 || 12 || 16 || 31 || 33
|}

列ごとに上が小さくなるようにソートする。
{| rules="cols" style="text-align:right"
| 1 || 3 || 7 || 12 || 14 || 10 || 8
|-
| 2 || 4 || 9 || 18 || 16 || 15 || 13
|-
| 5 || 6 || 11 || 19 || 17 || 22 || 26
|-
| 34 || 30 || 27 || 23 || 20 || 25 || 29
|-
| 35 || 32 || 28 || 24 || 21 || 31 || 33
|}

奇数行目は左が小さく、偶数行目は右が小さくなるようにソートする。
{| rules="rows" style="text-align:right"
| 1 || 3 || 7 || 8 || 10 || 12 || 14
|-
| 18 || 16 || 15 || 13 || 9 || 4 || 2
|-
| 5 || 6 || 11 || 17 || 19 || 22 || 26
|-
| 34 || 30 || 29 || 27 || 25 || 23 || 20
|-
| 21 || 24 || 28 || 31 || 32 || 33 || 35
|}

列ごとに上が小さくなるようにソートする。
{| rules="cols" style="text-align:right"
| 1 || 3 || 7 || 8 || 9 || 4 || 2
|-
| 5 || 6 || 11 || 13 || 10 || 12 || 14
|-
| 18 || 16 || 15 || 17 || 19 || 22 || 20
|-
| 21 || 24 || 28 || 27 || 25 || 23 || 26
|-
| 34 || 30 || 29 || 31 || 32 || 33 || 35
|}

奇数行目は左が小さく、偶数行目は右が小さくなるようにソートする。
{| rules="rows" style="text-align:right"
| 1 || 2 || 3 || 4 || 7 || 8 || 9
|-
| 14 || 13 || 12 || 11 || 10 || 6 || 5
|-
| 15 || 16 || 17 || 18 || 19 || 20 || 22
|-
| 28 || 27 || 26 || 25 || 24 || 23 || 21
|-
| 29 || 30 || 31 || 32 || 33 || 34 || 35
|}

列ごとに上が小さくなるようにソートする。
{| rules="cols" style="text-align:right"
| 1 || 2 || 3 || 4 || 7 || 6 || 5
|-
| 14 || 13 || 12 || 11 || 10 || 8 || 9
|-
| 15 || 16 || 17 || 18 || 19 || 20 || 21
|-
| 28 || 27 || 26 || 25 || 24 || 23 || 22
|-
| 29 || 30 || 31 || 32 || 33 || 34 || 35
|}

最後に、行ごとに左が小さくなるようにソートするとソートが完了する。
{| rules="rows" style="text-align:right"
| 1 || 2 || 3 || 4 || 5 || 6 || 7
|-
| 8 || 9 || 10 || 11 || 12 || 13 || 14
|-
| 15 || 16 || 17 || 18 || 19 || 20 || 21
|-
| 22 || 23 || 24 || 25 || 26 || 27 || 28
|-
| 29 || 30 || 31 || 32 || 33 || 34 || 35
|}