Реализация сортировки Шелла

include e:\masm32\include\masm32rt.inc
.data
  n dd ?                ; число элементов сортируемого массива.
  a dd ?                ; адрес массива в памяти. Как и в прошлый раз, массив будет
                        ; храниться в динамической памяти.
.code
                        ; Здесь нам снова потребуются традиционные для генерации массива процедуры:
                        ; randval, а также заполнение и вывод массива на экран.
                        ; Без долгих прелюдий привожу текст процедуры сортировки:
  sort proc             ; начнём с заполнения "массива" шагов. "А где
                        ; же объявлен массив?", - спросите вы. На самом деле
                        ; это будет не массив, я решил помещать шаги прямо в
                        ; стек по двум причинам:
                        ;   1) Занесение элементов в стек и извлечение их
                        ; оттуда осуществляется очень просто - командами push
                        ; и pop.
                        ;   2) Заметим, что вычисление шагов идёт по
                        ; возрастанию, а требоваться они нам будут наоборот –
                        ; в порядке убывания. Стек здесь идеально подходит.
    xor ecx, ecx        ; в регистре ЕСХ будем хранить индекс очередного
                        ; шага, хотя он нам не будет важен, важна будет
                        ; только его чётность, т. к. формула Седжвика сложная
                        ; и фактически состоит из двух формул - для чётных и
                        ; нечётных элементов последовательности.
    mov eax, 1          ; в регистрах EAX и EDX будем хранить степени двойки,
                        ; участвующие в формулах.
    mov edx, eax        ; присваиваем им начальные значения.
    .repeat             ; цикл, повторяющийся до тех пор, пока утроенная
                        ; величина очередного шага не превысит числа n.
      mov ebx, eax      ; чтобы не потерять значения степеней двоек при
                        ; дальнейших вычислениях, копируем их в регистры EBX
      mov esi, edx      ; и ESI.
      test ecx, 1       ; проверяем индекс очередного элемента на чётность.
      jz @else          ; в случае чётности переходим на метку @else.
        shl ebx, 3      ; пользуемся формулами Седжвика. Умножаем 2^i на 8.
        lea esi, [esi+esi*2]; хитрый способ умножения на 3...
        add esi, esi    ; ... и ещё на 2, т. е. на 6 в итоге.
        jmp @endif
      @else:
        lea ebx, [ebx+ebx*8]; вновь хитрое умножение, на этот раз на 9.
        lea esi, [esi+esi*8]; и здесь оно же.
        add edx, edx    ; берём следующую степень двойки при вычитаемом.
      @endif:
      sub ebx, esi      ; вычитаем из первого произведения второе...
      inc ebx           ; ... и увеличиваем выражение на 1
      shl ebx, 2        ; помня, что элементы сортируемого массива занимают в
                        ; памяти по 4 байта каждый, можем умножить значение
                        ; полученного шага на 4, чтобы потом "перепрыгивать"
                        ; на необходимое число байт.
      push ebx          ; полученный шаг помещаем в стек.
      add eax, eax      ; берём следующую степень двойки при уменьшаемом.
      lea ebx, [ebx+ebx*2]; полученное значение шага умножим на 3, чтобы
      mov esi, n        ; проверить, не превышает ли оно значение n*4.
      shl esi, 2
      inc ecx           ; берём следующий индекс.
    .until ebx>=esi     ; переходим в начало цикла, если нужны ещё шаги.
; Значения шагов находятся в стеке, можем приступать к сортировке.
    mov eax, a          ; нам понадобится адрес последнего элемента
                        ; сортируемого массива.
    mov ebx, n          ; вычислим его незатейливым и естественным способом.
    dec ebx             ; не забываем уменьшить на 1 иначе возможно обращение
                        ; не к той памяти.
    shl ebx, 2          ; не забываем также умножить на 4.
    add ebx, eax        ; искомый адрес теперь лежит в EBX.
    .repeat             ; проходим по значениям шагов, находящихся в стеке.
      pop eax           ; извлекаем значение очередного шага в байтах.
      mov edi, a        ; в регистр EDI кладём адрес массива а...
      mov ecx, edi      ; ... и запоминаем его значение в регистре ЕСХ, оно
                        ; понадобится далее при сравнении.
      add edi, eax      ; начинаем с элемента, равного очередному шагу...
      .while edi <= ebx ; ... и идём до последнего элемента.
        push edi        ; придётся запомнить значение EDI в стеке, так как
                        ; ниже оно может испортиться.
        mov edx, [edi]  ; регистр EDX используем как буфер.
        sub edi, eax    ; находим разность адресов текущего элемента и
                        ; элемента, стоящего на k шагов левее, где k –
                        ; текущее значение шага.
        @while:
          cmp edi, ecx  ; если EDI ушёл далеко влево за пределы массива...
          jb @endwhile  ; ... прерываем цикл.
          mov esi, [edi]; EDI находится внутри массива, значит нужно сравнить
                        ; значение элемента по адресу EDI с тем, который
                        ; находится в буфере, т. е. в регистре EDX.
          cmp edx, esi  ; производим это сравнение...
          jae @endwhile ; если буфер оказался меньше, выходим из цикла.
            mov [edi+eax], esi; помещаем этот элемент на k шагов правее.
            sub edi, eax; переходим на k шагов влево...
          jmp @while    ; ... и повторяем цикл.
        @endwhile:
        mov [edi+eax], edx; ставим на место элемент, лежащий в буфере
        pop edi         ; восстанавливаем старое значение EDI
        add edi, 4      ; повторяем внешний цикл для следующего элемента
      .endw
    .until eax==4       ; самый внешний цикл заканчиваем, когда значение шага
                        ; равно 1 (или 4 в байтах)
    ret
  sort endp