Русская Сортировка Половинами и quicksort быстрая сортировка qbasic и МЫ

летом 2018 года получено Свидетельство:
Русская сортировка половинами

на изображении часть свидетельства
без герба и без номеров и без ФИО

Z = N*(N-1)/2
Z = 4*(N/4*(N/4-1)/2+2*N/4)
Z = log(N;2)*(N/log(N;2)*(N/log(N;2)-1)/2+2*N/log(N;2))

Русская сортировка половинами важные действия визуализация

Russian sorting halves important actions visualisation

возможно сортировать буквы
однако вместо средней буквы в алфавите 
правильно вычислять интеграл букв

суммируя массив номеров букв
и разделив на количество элементов

получается средняя буква
проверено сортировкой тысяч элементов

и ускорение человеческой сортировки
думаю ускорит путь и время

сортировка олицетворяется в виде:
перемещается масса на расстояние

и важно используя наработки сортировок считывающих
одинаковый массив рассчитать интеграл:

работа как сумма произведений
массы груза на перемещения = работа

и пока рассчитано: там где требует
обычная сортировка интеграл работы 20

там моя Русская сортировка половинами
требует интеграл работы 12 значит
Русская сОртирОвка пОлОвинами лучше
 

На тему сортировка читая дюжину статей
с программами иногда часто вижу ляп:

для А элементов 2 вложенных массива
равные и число перестановок якобы А^2

зато правильнее: I от1 доА и J отI доА
и видимо те ошиблись пиша 1 вместо I
причём часто противореча пояснениям

для А=100 требуется А^2=10ооо ходов
а правильнее =100*(99)/2 =4950 ходов
2-жды меньше видно из формулы

и ещё вникнув в сортировку пополам
получается для А=100
=2*((100/2)*((100/2)-1)/2) = 2450 ходов
4-жды меньше чем советуют по интернету
и возможно реально делить на 4 части и
далее сортируется пузырьковая сортировка

Проведя эксперимент контролируя время
сортируя массив обратный от 100ооо до 1

qbasic: пополам 135 секунд и А^2 215 секунд
простой 389 секунд и А^2 497 секунд
чужие непонятные около 200 секунд

и вообще предполагаю используя мои строки
контролирующие время реально тестировать
многие алгоритмы сортировки на время

В свете вышесказанного: на тему сортировка и МЫ
обнаруживаются остроумные решения
ускоряющие тысячи операций в разы

Вдобавок создал строки контролирующие время
и возможно проверять на скорость варианты сортировки

Рекурсия доступна в вариантах Excel & QB64 Qbasic & C#

вкратце: рассчитываем средний элемент
и за 1 цикл раскидываем в начало и в конец
в другой массив и сортируем 2 части неравные раздельно

1-вые циклы лишь заполнение массива
специально худшими значениями и заодно
100ооо элементов сортировал за менее 120 секунд
1ооо сортирует за 0,05с за 274ооо проходов и 4600 перестановок

любителям сортировать ютюб

додумав деление на 4 участка

100ооо элементов наизнанку сортировались 66 секунд

деля на 4 части перешёл от имён в 2-мерный массив

известна формула количества проходов
= LOG(N) / LOG(2)
для создания вложенных циклов

общие строки при правильном расположении
внутри программы рассчитывают время

для сравнения сортировки многими алгоритмами
соблюдая универсальные имена переменных

n=100000
RANDOMIZE TIMER

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

start=TIMER: p=0: s=0

s=s+1 ' число циклов
p=p+1 ' число перестановок

finish=TIMER

FOR i=1 TO n: PRINT a(i);: NEXT

PRINT: PRINT: PRINT finish-start, s, p
END

оказывается худшими исходными данными
являются данные специально подготовленные
и подтверждается формула числа перестановок:
=2*4*3/2 = 12 перестановок и 6 перестановок

вместо изначальных =8*7/2 = 28 перестановок
и вместо массово ошибочного числа перестановок
=8^2 = 64 перестановок
12 перестановок в 5 раз быстрее
6 перестановок в 10 раз быстрее

в процессе соревнования сортировок
выявил 3 алгоритма basic и мой занимал 3-е место
отставая на доли секунды

и далее удалось оптимизировать как и предполагалось
в начале темы разделив массив пополам и ещё пополам

и посмотрев файл результатов всё отсортировано

10ооо ячеек за о,72 с а оппонент почти секунду
22ооо ячеек за 3,3 с а оппонент почти 5 сек
100ооо ячеек за 66 с а оппонент за 90 сек

Русская сортировка половинами все действия визуализация

Russian sorting halves all actions visualization

инструкция испытаний:
все программы содержат строки подключающие
одинаковый массив данных создаваемый управляемо
в виде 1/4-й разной мощности

в файле c:/N.txt указано количество и мощности
программа zapoln.exe формирует массив на c:/
сортировщики стартуя считывают одно и то же

и в процессе показывают одинаковые сообщения
и подсчитывают время чисто сортировки сообщая
на экране время и число проходов и перестановок
и сортировав пишут сортированное на c:/

Нобелевская премия сама себя не получит

реализовал подсчёт числа перестановок и проходов и создал
универсальные строки добавляемые в программы для сравнения

хоть bas хоть exe: конкурс сортировок и универсальная
оболочка: число ячеек n и признаки четвертей массива
abcd в файл c:/N.txt

zapoln.bas / ехе создаёт c:/ISX.txt с целью создать
области заполненные данными большими и малыми
и реально создавать любой массив
одинаковый для любого сортировщика

zapoln.bas

OPEN "c:/N.txt" FOR INPUT AS #5
INPUT #5, n, a, b, c, d

DIM d(n)

RANDOMIZE TIMER

FOR i=1 TO INT(n/4)
    d(i)=INT(RND*100*a)+a
    d(n/4+i)=INT(RND*100*b)+b
    d(n/2+i)=INT(RND*100*c)+c
    d(3*n/4+i)=INT(RND*100*d)+d
NEXT

OPEN "c:/ISX.txt" FOR OUTPUT AS #1

FOR i=1 TO n
PRINT #1, d(i): NEXT
END

встраиваем ключевые строки и тестируем и контролируем

OPEN "c:/N.txt" FOR INPUT AS #5
INPUT #5, n

DIM d(n)

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

FOR k=n-10 TO n: PRINT d(k);: NEXT: PRINT
start=TIMER: p=0: s=0

FOR i=1 TO n-1: FOR j=i TO n
        IF d(i) > d(j) THEN SWAP d(i), d(j): p=p+1
s=s+1: NEXT: NEXT

finish=TIMER

FOR i=n-10 TO n: PRINT d(i);: NEXT: PRINT
PRINT finish-start, s, p

OPEN "c:/REZ55.txt" FOR OUTPUT AS #2
FOR i=1 TO n: PRINT #2, d(i): NEXT
END

сортировка считывающая данные из c:/ISX.txt
и пишущая в ==sortda2yshz.txt

школьная сортировка и циклы и переменные

' DA 2 SIDE MASSIV sort
OPEN "c:/N.txt" FOR INPUT AS #5
INPUT #5, n

DIM d(2,n),q(3)

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

FOR k=n-10 TO n: PRINT d(1,k);: NEXT: PRINT
start=TIMER: p=0: s=0

FOR i=1 TO n: sum1=sum1+d(1,i): NEXT
sred1=sum1 / n: PRINT sred1: PRINT

y=1: z=0: FOR i=1 TO n
    IF d(1,i) < sred1 THEN d(2,y)=d(1,i): y=y+1: ELSE d(2,n-z)=d(1,i): z=z+1
    '    FOR k=1 TO n: PRINT d(2,k);: NEXT: PRINT
NEXT: PRINT

FOR i=1 TO n: sum2=sum2+d(2,i): NEXT
sred2=sum2 / n: PRINT sred2,y: PRINT

q(1)=1: q(2)=y-1: q(3)=n

FOR t=1 TO 2
    FOR i=q(t) TO q(t+1): FOR j=i+1 TO q(t+1)
            IF d(2,i) > d(2,j) THEN SWAP d(2,i),d(2,j): p=p+1
        s=s+1: NEXT: '    FOR k=1 TO n: PRINT d(2,k);: NEXT: PRINT
    NEXT
NEXT

finish=TIMER

FOR i=1 TO n: sum3=sum3+d(2,i): NEXT: sred3=sum3 / n: PRINT

FOR i=n-10 TO n: PRINT d(2,i);: NEXT: PRINT
PRINT finish-start, s, p

OPEN "c:/==sortda2yshz.txt" FOR OUTPUT AS #2
PRINT #2, finish-start; "секунд", "циклы"; s, "смены"; p
PRINT #2, n; "шт.", "школьная 2 части цикл и переменные"
FOR i=1 TO n: PRINT #2, d(2,i): NEXT

Пределы частей разделения массива избегают команду goto

Тестирование на одинаковых массивах

пузырьковая bubble = все со всеми: ошибочный массовый алгоритм из интернета
школьная = улучшенная пузырьковая: различные элементы без перестановки равных

русская сортировка: школьная или выбором включая деление на 2 части включает
цикл и переменные без индекса и улучшенная школьная и массив делится на 2 части
и также улучшается сортировка выбором и другие человеческие нормальные понятные
и возможно делить на 4 части

100ооо шт.   

1000 шт.  

во всех тестах формировался массив
где русская сортировка работает наиболее медленно

в интернете управляемая визуализация сортировок
airtucha.github.io/SortVis/
лучше выбирать число столбцов 25 поменьше
toptal.com/developers/sorting-algorithms/
sorting.at

growingwiththeweb.com/projects/sorting-visualiser/

algolab.valemak.com/thanos
algolab.valemak.com/
algolab.valemak.com/links

а также самостоятельно изучайте всевозможные сортировки в википедиях

shell сортировка

' SHELL сортировка

n = 100000
DIM a(n)

FOR i = 1 TO n: a(i) = INT((RND * 1000) + 5): NEXT
FOR k = n - 10 TO n: PRINT a(k);: NEXT: PRINT
start = TIMER

' algorithm

d = n \ 2
WHILE d > 0
 DO
 done = 1
 FOR i = 1 TO n - d
 IF a(i) > a(i + d) THEN
 SWAP a(i), a(i + d)
 done = 0
 END IF
 NEXT
 LOOP UNTIL done
 d = d \ 2
WEND

' algorithm

finish = TIMER
FOR i = n - 10 TO n: PRINT a(i);: NEXT: PRINT
PRINT finish - start
END

select сортировка выбором сравнивает текущий
с максимальным из оставшихся и переставляет местами

FOR i = 1 TO n - 1
    min = i
    FOR j = i + 1 TO n
        IF d(min) > d(j) THEN min = j
    NEXT j
    SWAP d(i), d(min)
NEXT i

самым быстрым Qbasic совместимым пока считаю

неизвестно где найденный алгоритм QuickSort Qsort
дополненный моими счётчиками

OPEN "c:/N.txt" FOR INPUT AS #5
INPUT #5, n

DIM x(n) AS LONG
DIM y(-1 TO n) AS LONG
y(-1) = 1

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

FOR k = n - 10 TO n: PRINT x(k);: NEXT: PRINT
start = TIMER: p = 0: s = 0

' algorithm

FOR i = 1 TO n
    y(x(i)) = y(x(i)) + 1: p = p + 1
NEXT i
 
FOR i = 1 TO n
    y(i) = y(i) + y(i - 1): p = p + 1
NEXT
 
FOR i = 0 TO n
    FOR j = y(i - 1) TO y(i)
        x(j) = i: p = p + 1
s = s + 1: NEXT j, i
 
' algorithm

finish = TIMER

FOR i = n - 10 TO n - 1: PRINT x(i);: NEXT: PRINT
PRINT finish - start, s, p

OPEN "c:/REZ11.txt" FOR OUTPUT AS #2
FOR i = 1 TO n: PRINT #2, x(i): NEXT: END

быстрее чем:  faster than:

медленнее чем: slower than:

Пока мир пытался ускорить быстрые алгоритмы
Россия ускорила медленные алгоритмы в 8 раз

While world was trying to speed up fast algorithms
Russia accelerated slow algorithms 8 times

and on eve of Certificate: Russian sorting halves

correctly read letter O:
Russkaya sOrtirOvka pOlOvinami

Sorting is represented as: mass moves to a distance
and it will be necessary to use results
sorts of reading same array calculate integral:

work as sum of works: load mass = displacement
and while calculated: where it requires normal sorting

Русская сортировка половинами: человеческая сортировка быстрее в 4 раза и МЫ

Цель: заинтересовать народ созданием программы
Русская сортировка половинами
на других любых языках программирования

Особенность программы «Русская сортировка половинами»:
уникальная картина сортировки и ускорение алгоритмов сортировки.


Допустим требуется сортировать массив N=11 чисел

Массив d(1,1...N)

Среднее значение: 6 как сумма данных ячеек делить на число ячеек

Массив d(2,1...N) и счётчик = 5

Любая из левых 5 ячеек меньше, чем любая из правых 6 ячеек.

Массив d(2,1...N) условно делится на 2 части:

и ячейки проходят ещё циклы независимо друг от друга,
сохраняя непрерывность массива d(2,1...N).

Сравнение формул для оценки максимального ускорения других сортировок

текстовые строки

Русская сортировка половинами ускоряет другие сортировки
за счёт перехода формулы затрат времени N^2 или N*(N-1)/2
в формулу например для 2-х частей: 2*(N/2)*((N/2)-1)/2.

Z = N*(N-1)/2
Z = 4*(N/4*(N/4-1)/2+2*N/4)
Z = log(N;2)*(N/log(N;2)*(N/log(N;2)-1)/2+2*N/log(N;2))
 

Русская сортировка половинами требует данные:
c:/N.txt = только количество элементов и
c:/ISX.txt = элементы в столбец в требующемся количестве возможно создать в excel
=случмежду(1000;100000)
и скопировав вставить текст в c:/ISX.txt

'RUSSIAN sorting halves 4 part bubble
N=17539
DIM d(N), a(N), v(N), q(5)
RANDOMIZE TIMER: FOR i=1 TO N: d(i)=INT(RND * N): NEXT
FOR k=1 TO 10: PRINT d(k);: NEXT: PRINT: FOR k=N-9 TO N: PRINT d(k);: NEXT: PRINT: PRINT

start=TIMER: s=0

' ALL
summa=0: FOR i=1 TO N: summa=summa+d(i): NEXT: middle=summa/N: y=1: z=0
FOR i=1 TO N
IF d(i) < middle THEN a(y)=d(i): y=y+1: ELSE a(N-z)=d(i): z=z+1
NEXT
q(3)=y-1
PRINT "ALL middle="; middle
FOR k=1 TO 10: PRINT a(k);: NEXT: PRINT: FOR k=N-9 TO N: PRINT a(k);: NEXT: PRINT: PRINT

'1 FROM 2
summa=0: FOR i=1 TO q(3): summa=summa+a(i): NEXT: middle=summa/q(3): y=1: z=0
PRINT "1 FROM 2="; middle, "1 ..."; q(3)
FOR i=1 TO q(3)
IF a(i) < middle THEN v(y)=a(i): y=y+1: ELSE v(q(3)-z)=a(i): z=z+1
NEXT
FOR k=1 TO 10: PRINT v(k);: NEXT: PRINT: FOR k=q(3)-9 TO q(3): PRINT v(k);: NEXT: PRINT: PRINT
q(2)=y-1

'2 FROM 2
summa=0: FOR i=q(3)+1 TO N: summa=summa+a(i): NEXT: middle=summa/(1+N-q(3)): y=q(3): z=0
PRINT "2 FROM 2="; middle, q(3)+1; "..."; N
FOR i=q(3) TO N
IF a(i) < middle THEN v(y)=a(i): y=y+1: ELSE v(N-z)=a(i): z=z+1
NEXT
FOR k=q(3) TO q(3)+10: PRINT v(k);: NEXT: PRINT: FOR k=N-9 TO N: PRINT v(k);: NEXT: PRINT: PRINT
q(4)=y-1: q(1)=2: q(5)=N

' SORTING
PRINT "1="; 1, "2="; q(2), "3="; q(3), "4="; q(4), "5="; N: PRINT
FOR t=1 TO 4
FOR i=q(t)-1 TO q(t+1): FOR j=i+1 TO q(t+1)
IF v(i) > v(j) THEN SWAP v(i), v(j): s=s+1
NEXT: NEXT: NEXT

finish=TIMER

FOR k=1 TO 10: PRINT v(k);: NEXT: PRINT: FOR k=N-9 TO N: PRINT v(k);: NEXT: PRINT: PRINT
PRINT "DA RUS 4 ", finish-start; "second ", "swap "; s

OPEN "c:/RUsortdav4.txt" FOR OUTPUT AS #2
PRINT #2, finish-start; "second ", "swap "; s
PRINT #2, N; "Russian sorting halves 4 parts bubble "
FOR i=1 TO 20: PRINT #2, v(i): NEXT
FOR i=N-19 TO N: PRINT #2, v(i): NEXT

start=TIMER: s=0
FOR i=1 TO N: FOR j=i+1 TO N
IF d(i) > d(j) THEN SWAP d(i), d(j): s=s+1
NEXT: NEXT
finish=TIMER

PRINT "BUBBLE ", finish-start; "second ", "swap "; s: END

деление массива на 4 части происходит мгновенно
имя q(3) будет заменено на имя попроще

но попытки разделения за 2 вложенных циклов
разбиваются о порядок точек середин 3 2 4

что приводит к массивам с 2-йными скобками
что усложняет понимание и лучше применить

говорящие переменные типа средний3
оставив 3 цикла раздельными

Цель: заинтересовать народ созданием программы Русская сортировка половинами
на других любых языках программирования

Нобелевская премия сама себя не получит
Nobel Prize will not receive itself
Le prix Nobel ne se recevra pas

rosettacode.org/wiki/Category:Sorting_Algorithms

airtucha.github.io/SortVis/
toptal.com/developers/sorting-algorithms/
sorting.at

growingwiththeweb.com/projects/sorting-visualiser/

anim.ide.sk/sorting_algorithms_1.php

algolab.valemak.com/thanos
algolab.valemak.com/
algolab.valemak.com/links

algolab.valemak.com/algolab-xlsm
 

Русская сортировка половинами важные действия визуализация
Russian sorting halves important actions visualization

RussianSortingHalvesDAV.bas: рекурсия QB64 Qbasic QuickBasic Basic рекурсия

ускоряющее развитие:
вместо 2-мерного массива 2 массива d(N) и a(N)
и действительно успешно: сортирует 100ооо за 0,22 секунды

сортирует 1000ооо за 2,2 секунды
сортирует миллион за 2,2 секунды
sorts 1'000'000 in 2.2 seconds
сортирует 1'000'000 за 2,2 секунды

' Russian Sorting Halves Danilin

DECLARE SUB RussianSortingHalvesDAV (ab!, yz!, part!, age!)
CLOSE
OPEN "c:/N.txt" FOR INPUT AS #5
INPUT #5, n: PRINT n

'n=123456

age=1+LOG(n)/LOG(2)
PRINT n, age

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

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

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

IF n < 17 THEN FOR k=1 TO n: PRINT d(k);: NEXT: PRINT
IF n > 16 THEN FOR k=n-8 TO n: PRINT d(k);: NEXT: PRINT

start=TIMER

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

finish=TIMER

IF n < 17 THEN FOR k=1 TO n: PRINT d(k);: NEXT: PRINT
IF n > 16 THEN FOR k=n-8 TO n: PRINT d(k);: NEXT: PRINT

PRINT finish-start

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

FOR k=1 TO 20: PRINT d(k);: NEXT: PRINT: PRINT
FOR k=n-9 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

PureBasic Русская Сортировка Половинами и скорая и человеческая
PureBasic Russian Sorting Halves and fast and human

считывает только количество из c:/N.txt
удобно чтобы обходиться без оболочки PureBasic
и сортировав пишет только по 1000 элементов
наименьших и наибольших в c:/RSH_DAV.txt

сортирует 1000ооо за 0,3 секунды
сортирует миллион за 0,3 секунды
sorts 1'000'000 in 0.3 seconds
сортирует 1'000'000 за 0,3 секунды

; Russian Sorting Halves Danilin
OpenConsole()
Declare RussianSortingHalvesDAV (ab, yz, part, age)

;n=12345678

If ReadFile(0, "c:/N.txt")
 n=Val(ReadString(0))
 CloseFile(0)
EndIf

age=Int(1+(Log(n)/Log(2)))
Global Dim d(n)
Global Dim a(n)

For i=1 To n
 ;d(i)=Random(n,1) ; случайные значения от 1 до n
 d(i)=n-i+1;
Next

 ; вывод исходных значений до сортировки
PrintN(" Исходный без сортировки Первые 20")
For k=1 To 20: Print(" "+ d(k)): Next: PrintN("")
PrintN(" Последние 10")
For k=n-9 To n : Print(" "+ d(k)): Next: PrintN("")

start=ElapsedMilliseconds() ; таймер

If age > 0 :
 RussianSortingHalvesDAV(1, n, 1, age)
EndIf

finish=ElapsedMilliseconds() ; таймер

PrintN("RussianSorting Первые 50")
For k=1 To 50: Print(" "+ d(k)): Next: PrintN("")
PrintN(" Последние 20")
For k=n-19 To n : Print(" "+ d(k)): Next: PrintN("")

PrintN( "Время сортровки RussianSorting=" + Str(finish-start))

If OpenFile(0, "c:/RSH_DAV.txt")
 For k=1 To 1000 :WriteString (0, " " +d(k)): Next
 For k=n-1001 To n :WriteString (0, " " +d(k)): Next
 CloseFile(0)
EndIf

Input()
End

; Процедура сортировки
Procedure RussianSortingHalvesDAV (ab, yz, part, age)

If yz-ab < 1 :ProcedureReturn 0
EndIf

For i=ab To yz
summa=summa+d(i)
Next
middle=summa/(yz-ab+1)

abc=ab-1
xyz=yz+1

For j=ab To yz
If d(j) <= middle:
abc=abc+1: a(abc)=d(j)
Else
xyz=xyz-1: a(xyz)=d(j)
EndIf

Next

For w=ab To yz: d(w)=a(w): Next

If part < age :
If abc >= ab :RussianSortingHalvesDAV(ab, abc, part+1, age)
EndIf
If xyz < yz :RussianSortingHalvesDAV(xyz, yz, part+1, age)
EndIf
EndIf

EndProcedure

C#

// RUSSIAN SORTING HALVES DANILIN C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
namespace davApp
{
class Program
{
private long age;
static long[] a;
static long[] d;

static void Main(string[] args)
{
int n=0;
// read numbers
var inpFile=new StreamReader("N.txt");
n=Convert.ToInt32(inpFile.ReadLine());
inpFile.Close();

var age=1+Math.Log(n) / Math.Log(2);

Console.WriteLine(n);

a=new long[n+1];
d=new long[n+1];

for (int i=1; i<=n; i++)
d[i]=n-i+1;

// RANDOM [1;n]
//var rand=new Random();
//for (int i=1; i<=n; i++)
// d[i]=rand.Next(1, n);

// read N line from file
//inpFile=new StreamReader("ISX.txt");
//for (int i=1; i<=n; i++)
// d[i]=Convert.ToInt64(inpFile.ReadLine());
//inpFile.Close();

// write on screen
int m=Math.Min(n, 20);
for (int i=1; i<=m; i++)
Console.Write("{0} ", d[i]);
Console.WriteLine();

// RUSSIAN SORTING HALVES
var start=DateTime.Now;
if (age>0)
dav(1, n, 1, age);
var finish=DateTime.Now;

Console.WriteLine("{0} second", (finish-start).TotalSeconds);

// WRITE ON SCREEN
Console.WriteLine("[1..{0}]", m);
for (int i=1; i<=m; i++)
Console.Write("{0} ", d[i]);
Console.WriteLine();

// write on screen
Console.WriteLine("[{0}..{1}]", n-m+1, n);
for (int i=n-m+1; i<=n; i++)
Console.Write("{0} ", d[i]);
Console.WriteLine();

// write in file
var outFile=new StreamWriter("dav.txt");
for (int i=1; i<=m; i++)
outFile.WriteLine(d[i]);
outFile.WriteLine();

for (int i=n-m+1; i<=n; i++)
outFile.WriteLine(d[i]);
outFile.WriteLine();
outFile.Close();

Console.WriteLine("Press any key");
Console.ReadKey();
}

static void dav(int ab, int yz, int part, double age)
{
if (yz-ab<1)
return;

long summa=0;
for (int i=ab; i<=yz; i++)
summa=summa+d[i];

double middle=summa / (yz-ab+1.0);

var abc=ab-1;
var xyz=yz+1;

for (int i=ab; i<=yz; i++)
if (d[i]<middle)
{
abc=abc+1;
a[abc]=d[i];
}
else
{
xyz=xyz-1;
a[xyz]=d[i];
}

for (int i=ab; i<=yz; i++)
d[i]=a[i];

if (part<age)
{
if (abc>=ab) dav(ab, abc, part+1, age);
if (xyz<=yz) dav(xyz, yz, part+1, age);
}
return;
}
}
}

Прототип сортирует интеграл букв:
и строки нижние больше верхних

N=10: DIM d$(N), a$(N), b(27)

d$(1)="ABC": d$(2)="QQQ": d$(3)="SSS": d$(4)="ZYX": d$(5)="PPP":
d$(6)="FFF": d$(7)="QBB": d$(8)="DDD": d$(9)="ZZZ": d$(10)="AAA":

FOR i=1 TO N
 c=ASC(MID$(d$(i),1,1))-64
 b(c)=b(c)+1
NEXT

FOR i=1 TO 27 STEP 3: PRINT CHR$(i+64); b(i), CHR$(i+1+64); b(i+1), CHR$(i+2+64); b(i+2): NEXT

PRINT: summa=0: FOR i=1 TO 26: summa=summa+i * b(i): NEXT
h=0: FOR i=1 TO 26
 IF b(i) > 0 THEN h=h+1
NEXT

middle=summa/h: PRINT summa, h, middle: PRINT

y=1: z=0: FOR i=1 TO N
 c=ASC(MID$(d$(i), 1, 1))-64: PRINT c; c * b(c),
 IF c * b(c) < middle THEN a$(y)=d$(i): y=y+1: ELSE a$(N-z)=d$(i): z=z+1
NEXT: PRINT: PRINT

FOR i=1 TO N: PRINT a$(i),: NEXT: PRINT
PRINT y-1

Ещё результат экспериментов для предыдущего языка:
копия массива результатов в данные только целиком ухудшает
и больше преуспеют языки где есть быстрый подсчёт суммы
и копирование части массива результатов в массив данных

Замена числа 1 везде на переменную с именем
например one проверено для разных типов данных:
ускорила qb64 с 2,2 до 2,09 секунд
и замедлила pb с 0,3 до 0,4 секунд
для сортировки 1'000'000 элементов

Русская Сортировка Третями
распределяющая: меньше трети и больше двух третей
выглядит бесконечно при рекурсии
ведь непонятно как переходить между третями

В то время как Русская сортировка половинами делит
массив на 2/4/8 частей как Русская Сортировка Осьмушками
 

Русская Сортировка Половинами и скорая и человеческая
замечательная задача для Олимпиад по информатике

Russian Sorting Halves and fast and human
is wonderful job for Olympiad in computer science

Русская сортировка половинами помогает изучить:

массивы многомерные
рекурсия
логарифм
интеграл
чтение с диска
присваивание
типы данных
вычисление
случайные
сумма
среднее
условие
обмен
время
инкремент
декремент
циклы вложенные
индексы индексов
варианты условий
варианты циклов
вывод на экран
запись на диск

Данная тема развивается на форумах:

qb64forum.alephc.xyz/index.php?topic=702

bytes.com/topic/c-sharp/answers/971639-russian-sorting-halves-danilin
csharpforums.net/threads/russian-sorting-halves-danilin.4221
go4expert.com/forums/russian-sorting-halves-danilin-t35231/
forums.purebasic.com/english/viewtopic.php?f=13&t=71585
freebasic.net/forum/viewtopic.php?f=3&t=27097

rosettacode.org/wiki/Category:Sorting_Algorithms

Созданы 13 вариантов Русская сортировка половинами

1. Ускорение сортировки пузырьковой в 2 раза
добавив строки деления массива на 2 части

2. Ускорение сортировки пузырьковой в 4 раза
добавив строки деления массива на 4 части

3. Ускорение сортировки выбором в 2 раза
добавив строки деления массива на 2 части

4. Ускорение сортировки выбором в 4 раза
добавив строки деления массива на 4 части

5. Рекурсия QB64 1'000'000 за 2,2 секунды
6. Рекурсия PureBasic 1'000'000 за 0,3 секунды
7. Рекурсия C# 1'000'000 за 0,2 секунды
8. Рекурсия FreeBasic 1'000'000 за 0,15 секунды
9. QB64 сортирует интеграл букв

10. Excel ускоренная для 250 элементов
11. Excel анимационная для 250 элементов

12. Ускорение пузырьковой сортировки
делением на 4 части C#
13. Вложенные циклы и индексы индексов
 

Русская Сортировка Интегралов

Russian Sorting of Integrals

qb64 Seven Bubble sort for you: which do you choose? 
qb64phoenix.com/forum/showthread.php?tid=1540&pid=14341#pid14341
 

kenokeno.ucoz.ru/fips/2018618246.htm