Russian Sorting Halves Danilin

[DANILIN]

Russian Sorting Halves and fast and human
sorts 1'000'000 in 2.2 seconds on QB64
sorts 1'000'000 in 0.3 seconds on PureBasic

me interested implementation of algorithm in language Python

number of elements is written to file with c:/N.txt or use variable n
array d(n) can be read from a file or synthesized in a program

' Russian Sorting Halves Danilin

DECLARE SUB RussianSortingHalvesDAV (ab!, yz!, part!, age!)
CLOSE
OPEN "c:/N.txt" FOR INPUT AS #1
INPUT #1, n
'n=1234567
age = 1 + LOG(n) / LOG(2)
PRINT n

DIM SHARED d(n) 'AS LONG
DIM SHARED a(n) 'AS LONG

'OPEN "c:/ISX.txt" FOR INPUT AS #2
'FOR i=1 TO n: INPUT #2, d(i): NEXT

'FOR i = 1 TO n: d(i) = n - i + 1: NEXT ' INT(RND*n)
FOR i = 1 TO n: d(i) = INT(RND * n): NEXT '

FOR k = 1 TO 20: PRINT d(k);: NEXT: PRINT: PRINT
FOR k = n - 19 TO n: PRINT d(k);: NEXT: PRINT: PRINT

start = TIMER

IF age > 0 THEN
    CALL RussianSortingHalvesDAV(1, n, 1, age)
END IF

finish = TIMER

PRINT finish - start; "second ": PRINT

OPEN "c:/=RuSortHalves_dav.txt" FOR OUTPUT AS #3
PRINT #3, finish - start; "second "
PRINT #3, n; "elements", "RECURSION"
FOR i = 1 TO 22: PRINT #3, d(i): NEXT
FOR i = n - 22 TO n: PRINT #3, d(i): NEXT

FOR k = 1 TO 20: PRINT d(k);: NEXT: PRINT: PRINT
FOR k = n - 19 TO n: PRINT d(k);: NEXT: PRINT: PRINT

END

SUB RussianSortingHalvesDAV (ab, yz, part, age)

IF yz - ab < 1 THEN EXIT SUB

FOR i = ab TO yz
    summa = summa + d(i)
NEXT
middle = summa / (yz - ab + 1)

abc = ab - 1
xyz = yz + 1

FOR i = ab TO yz
    IF d(i) < middle THEN abc = abc + 1: a(abc) = d(i): ELSE xyz = xyz - 1: a(xyz) = d(i)
NEXT

FOR i = ab TO yz: d(i) = a(i): NEXT

IF part < age THEN
    IF abc >= ab THEN CALL RussianSortingHalvesDAV(ab, abc, part + 1, age)
    IF xyz <= yz THEN CALL RussianSortingHalvesDAV(xyz, yz, part + 1, age)
END IF

END SUB

Russian Sorting Halves Danilin visualisation
https://www.youtube.com/watch?v=UxvSwOtpiuc
https://www.youtube.com/watch?v=9poxfAcbxFQ

[Image: rusortpol10.gif]

me interested implementation of algorithm in language Python