が面白かったので、Haskellコードからreverseを粛正してみる。

俺実装

import Data.List
import Test.QuickCheck

-- 残りが出なくなるまでスターリンし、シベリア帰りとマージする
stalinMergeSort :: Ord a => [a] -> [a]
stalinMergeSort xs =
  case stalin xs of
    (as, []) -> as
    (as, bs) -> merge as $ stalinMergeSort bs

-- 整列した列と残りに分ける
stalin :: Ord a => [a] -> ([a],[a])
stalin xs = foldr step ([],[]) xs
  where
    step v ([],bs) = ([v],bs)
    step v (as@(a:_), bs)
      | v <= a    = (v:as, bs)
      | otherwise = (as, v:bs)

-- 前から確定させたい人向けの別実装
stalin2 :: Ord a => [a] -> ([a],[a])
stalin2 [] = ([],[])
stalin2 (x:xs) = loop x xs
  where
    loop v [] = ([v], [])
    loop v (x:xs)
      | v <= x    = fstcons v $ loop x xs -- let (as,bs) = loop x xs in (v:as, bs)
      | otherwise = sndcons x $ loop v xs -- let (as,bs) = loop v xs in (as, x:bs)

    fstcons, sndcons :: a -> ([a],[a]) -> ([a],[a])
    fstcons x (ys,zs) = (x:ys,zs)
    sndcons x (ys,zs) = (ys,x:zs)

-- いつものマージ
merge :: Ord a => [a] -> [a] -> [a]
merge xxs@(x:xs) yys@(y:ys) =
  case compare x y of
    LT -> x : merge xs yys
    EQ -> x : y : merge xs ys
    GT -> y : merge xxs ys
merge xs [] = xs
merge [] ys = ys

prop :: [Int] -> Bool
prop xs = sort xs == stalinMergeSort xs

計算量

全てを等分してからマージしていく、普通のマージソートは $O(N \log N)$ になる。
全体を半々に割るトップダウンの向きでなく、ボトムアップにマージしていく変種で書いてみる。

mergeSort :: Ord a => [a] -> [a]
mergeSort [] = []
mergeSort xs = head . until isSingleton mstep . map singleton $ xs

mstep (xs:ys:xss) = merge xs ys : mstep xss
mstep xss = xss

isSingleton [_] = True
isSingleton  _  = False

マージは統合後の要素数で $O(N)$ かかり、マージソート全体は、分割して再帰する段数だけこれを繰り返すので $O(N \log N)$ となる。

これと比較すると、スターリン・マージソートは、長さ1のリストから始める代わりに、整列済みな部分列を取り出してはマージの対称にするため、同様に高速でもいい気もする。そうならないのは、マージが一方通行になっているため、繰り返しの高さが$N$になってしまい、結局$O(N^2)$になっている。
なのでそこを改善する。

俺実装（改善版）

stalinMergeSort2 :: Ord a => [a] -> [a]
stalinMergeSort2 [] = []
stalinMergeSort2 xs = head . until isSingleton mstep . unfoldr sstep $ xs
  where
    sstep [] = Nothing
    sstep xs = Just $ stalin xs

これなら $O(N \log N)$ になっていると思う。

追記 Python版

書いた。

def stalin_mergesort2(target:list):
    # スターリン・マージソート2
    def _merge(rlist:list, llist:list) -> list: # 変更なし
        returnlist = []
        rindex = 0
        lindex = 0
        while rindex != len(rlist) and lindex != len(llist):
            if rlist[rindex] >= llist[lindex]:
                returnlist.append(llist[lindex])
                lindex += 1
            else:
                returnlist.append(rlist[rindex])
                rindex += 1
        returnlist.extend(rlist[rindex:])
        returnlist.extend(llist[lindex:])
        # print(returnlist)
        return returnlist

# 誰もいなくなるまでスターリンを繰り返す
    xs = target # スターリン処理対象
    sed = []    # スターリンソート済み列リスト
    while len(xs) > 0 :
        ys = [xs[0]]
        xindex = 1   # 先頭をyへ送る
        zs = []
        for x in xs[1:] :
            if ys[-1] <= x:
                ys.append(x)
            else:
                zs.append(x)
        sed.append(ys)
        xs = zs

# 2つを1つにマージすることを、一つになるまで繰り返す
    while len(sed) > 1 :
        ws = []
        for i in range(0, len(sed) - 1, 2):
            ws.append(_merge(sed[i],sed[i+1]))
        if len(sed) % 2 == 1 :
            ws.append(sed[-1])
        sed = ws

    return sed[0]

結果。

速くはなったけどまともなやつより遅いまま、という感じかな。

スターリン・マージソートですって。

俺実装

計算量

俺実装（改善版）

追記 Python版