シェアソートを使用する

シェアソート (shear sort) は、要素を 正方形の格子（√n × √n） に並べたうえで、行 と 列 を交互に整列させていく比較ベースのソートである。

本質的には次の二種類のフェーズを繰り返す。

  1. 行フェーズ: 各行を、偶数行は左から昇順・奇数行は右から昇順（左へ値が大きくなる並び）になるように整える。いわゆる 蛇行方向が交互になる行ソート である。
  2. 列フェーズ: 各列を、上から下へ 昇順 になるように整える。

格子の一辺の長さを r とすると、繰り返しはだいたい O(log r) 回で十分であり、全体として並列ステップ数は Θ(r log r)（要素数 N=r² に対して Θ(√N log N)）に収まるとされる。出力の並びは一般に 蛇行順で値が昇順になる配置 になる。

バブルソートやクイックソートが 一次元のインデックス列 を直接いじるのに対し、シェアソートは 二次元インデックスと「同じ行・同じ列だけが比較される」という通信制約 が前提になる点が対照的である。

procedure shear_sort_rows_then_cols(A, side)
  repeat until snake_order_sorted(A, side)
    for row from 0 to side - 1
      if row is even then
        sort_row_ascending_left_to_right(A, row)
      else
        sort_row_descending_left_to_right(A, row)
    for col from 0 to side - 1
      sort_column_ascending_top_to_bottom(A, col)

蛇行順で昇順になった時点では、行優先に左から読むとまだ入れ替わったように見えることがある。実運用や見やすい一次元配列に落とすときは、文献でも触れられるように 仕上げでもう一度だけ行方向に処理を足す（このデモでは 各行をすべて昇順にそろえる）と、行優先読みでも昇順になる。

一次元配列だけを対象にしたバブルソートやクイックソートのデモと見比べると、列の交換では画面上離れた二本の棒が動く一方で、行内の交換は隣同士に見えるという違いがはっきりする。