g | x | w | all
Bytes Lang Time Link
091APLDyalog Unicode240724T120115Zovs

APL(Dyalog Unicode), 91 bytes SBCS

{1≥n←≢⍵:0⋄+/(⍵{(×l)++/∧\⊃=/⍺⍵↑⍨¨l←⍺⌊⍥≢⍵}¨(⍵,⊂⍬)[r⍳{⍵+m=(m,2)[r⍳⍵]}⍣≡r←⍋⍋⍵]),∇¨⍵⊂⍨≠m←n<2×⍳n}

Try it on APLgolf!

A recursive function computing the total number of comparisons. Rough breakdown:

1≥n←≢⍵:0. If there is only a single string in the list, no comparisons are needed.

∇¨⍵⊂⍨≠m←n<2×⍳n. Split the list into two halves, call the function recursively.

⍵ ... (⍵,⊂⍬)[r⍳{⍵+m=(m,2)[r⍳⍵]}⍣≡r←⍋⍋⍵]. Match up each string with the next larger string in the other half.

{(×l)++/∧\⊃=/⍺⍵↑⍨¨l←⍺⌊⍥≢⍵}¨ For each pairing, count the necessary character comparisons to sort.


APL(Dyalog Unicode), 95 bytes SBCS

There is probably some better way to implement the grouping function, would be 24 bytes shorter if the input length was a power of 2.

{+/1+{+/∧\⊃=/⍺⍵↑⍨¨⍺⌊⍥≢⍵}/⍵[⍋⍵][↑⍸(××≠⍤1)k×⍉∧\×k←⊃⍤⍸¨∘.≠⍨↓↑({1=⍵:0⋄⊃,/1 2,¨¨∇¨(⌊,⌈)⍵÷2}≢⍵)[⍋⍵]]}

Try it on APLgolf!