この論文によると、Knuthのgap式よりも性能の良いものがいくつか提案されているようです。その中のTokudaの式を使うことにします。
■実行結果
確かにKnuthのものより計算量が少なくなっていて、Quick sortと似たような要素数依存性(O(NlogN))を見せています。再帰も要らなければテンポラリメモリーも要らないShell sortに、こんな秘められた力があったとは!Shell sort かわいいよ Shell sort!
■ソースコード
必要なオプション
/assume:realloc_lhs
MODULE m_sort IMPLICIT NONE CONTAINS PURE FUNCTION ssort(x) ! Shell Sort REAL, ALLOCATABLE :: ssort(:) REAL, INTENT(IN) :: x(:) REAL :: tmp INTEGER :: i, j, k, kmax, igap ssort = x kmax = 0 DO IF ( INT( (9.0 * (9.0 / 4.0)**(kmax + 1) - 4.0) / 5.0 ) > SIZE(x) * 4.0 / 9.0 ) EXIT kmax = kmax + 1 END DO DO k = kmax, 0, -1 igap = INT( (9.0 * (9.0 / 4.0)**k - 4.0) / 5.0 ) ! Tokuda's gap sequence DO i = igap, SIZE(x) DO j = i - igap, 1, -igap IF ( ssort(j) > ssort(j + igap) ) THEN tmp = ssort(j) ssort(j) = ssort(j + igap) ssort(j + igap) = tmp ELSE EXIT END IF END DO END DO END DO RETURN END FUNCTION ssort END MODULE m_sort !======================================================== PROGRAM sort USE m_sort IMPLICIT NONE REAL, ALLOCATABLE :: x(:), y(:) REAL :: t0, t1 INTEGER :: i CALL RANDOM_SEED() DO i = 0, 9 ALLOCATE( x(10**i) ) CALL RANDOM_NUMBER(x) CALL CPU_TIME(t0) y = ssort(x) CALL CPU_TIME(t1) PRINT *, i, SIZE(x), t1 - t0 DEALLOCATE( x, y ) END DO STOP END PROGRAM sort