Пользователь
0,0
рейтинг
9 мая 2014 в 11:46

Разработка → Аппаратный сортировщик чисел на verilog-е tutorial

В этой моей статье, как и в предыдущей рассматривается цифровая схемотехника с точки зрения программиста. Но в этот раз будет разобрана «более алгоритмическая» задача сортировки чисел, с разбором verilog-кода. Рассматриваемое аппаратное решение позволяет отсортировать n чисел за время 2*n. На картинке ДПВ показан вывод на монитор от тестового проекта для ПЛИС, там каждой линии соответствует один тик сортировщика, сначала n тиков случайные числа записываются в сортировщик, затем n тиков выводятся числа отсортированные.





Известно, что программная сортировка n чисел в общем случае требует время O(n*log(n)). Аппаратная же позволяет обойти это ограничение, за счёт выполнения нескольких сравнений сразу, см. например сети сортировки. Сеть сортировки работает целиком параллельно, данные приходят и уходят вместе, мой же модуль принимает или выдаёт только одно число за раз, но не требует дополнительного времени: Сначала в буфер записывается N < Nmax чисел за N тактов, затем N тактов оттуда читается (забирается) отсортированная последовательность.
UPDATE: в комментариях меня убедили, что это не даёт права говорить о сложности алгоритма o(n). Если N>Nmax, то сортировать придётся по частям, используя затем сортировку слиянием, затраченное время будет ~N*log(N/Nmax). При N -> inf это даст те же O(n*log(n)). Это, однако не отменяет того факта, что аппаратная сортировка работает быстрее программной.

На картинке дано условное описание основной версии алгоритма. Надеюсь, смысл можно уловить.


Посмотрим на исходники на verilog-е. Напомню главное отличие HDL от языка программирования — язык программирования это инструкция для исполнителя, которая исполняется последовательно, строчка за строчкой, а программа на HDL соответствует электронной схеме, все части которой работают одновременно.

Разберём исходник сортировщика - цепочки.
Определяем модуль всей цепочки. у него есть входы, выходы и внутренние модули, всё это надо связать в единую сеть с помощью комбинационной схемы. Регистров тут в явном виде нет, они инкапсулированы внутри сортировочных ячеек.

//	Заголовок
module Sorting_Stack ( clk, hold, is_input, data_in, data_out	);

//	Числовые параметры
parameter HBIT= 15;				//	size of number in bits
parameter R_SZ= 256;				//	capacity, max sequence size
parameter _R_SZ= (R_SZ+1)/2;			//	not to modify

//	Перечисляем входы-выходы схемы
//	Тактовый сигнал
input clk;
...
//	входы-выходы данных
input [HBIT:0] data_in;		//	load one number per clock
output [HBIT:0] data_out;	//	while is_input==0, max value popping out here
//	в квадратных скобках перед именем - разрядность
...
//	Промежуточные точки схемы
wire [HBIT:0] in_prev[_R_SZ];
wire [HBIT:0] in_next[_R_SZ];
wire [HBIT:0] out[_R_SZ];
//	в квадратных скобках после имени - размерности массивов

//	Внутренние подмодули модуля
//	Здесь определён целый массив подмодулей
// storage
Cell_Compare #(HBIT) ribbon[_R_SZ] ( clk, hold, is_input, in_prev, in_next, out );

Рассмотрим подробнее подстановку одного модуля в другой
Cell_Compare — тип модуля
#(HBIT) — установка числовых параметров
ribbon — имя экземпляра
[_R_SZ] — это массив, указываем количество
( clk, hold, is_input, — общие сигналы для всех
in_prev, in_next, out ); — специфические сигналы для каждого элемента массива.

Далее generate — полезная конструкция, которая позволяет
применять циклы и т.д. при описании комбинационных схем.

//	Соединяем некоторые точки схемы
generate
  genvar i,j;
  for (i=0; i<_R_SZ-1; i=i+1) 
  begin : block_name01
		assign in_prev[i+1]= out[i];
		assign in_next[i]= out[i+1];
  end
  assign in_prev[0]= data_in;
  assign data_out= out[0];
  assign in_next[_R_SZ-1]= 0;
endgenerate

endmodule

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

module Cell_Compare ( clk, hold, is_input, in_prev, in_next, out );

parameter HBIT= 15;


input clk;
input hold;

input is_input;

input [HBIT:0] in_prev;
input [HBIT:0] in_next;

Здесь начинается собственно логика сортировки. Каждая ячейка хранит два числа, одно меньше другого. Каждый такт (если не hold) ячейка сравнивает число, пришедшее от соседа со своим «чемпионом». Чемпион — максимальное число при записи и минимальное при чтении. Проигравший покинет ячейку на следующем такте. В результате, данные движутся по цепочке сначала в одном направлении, потом в другом. Количество чисел, помещающихся в устройстве равно удвоенному количеству ячеек.

Вернёмся к исходному коду. Здесь при описании выхода применён селектор, (скомпилируется в мультиплексор). is_input определяет, читаем мы данные или пишем, от него зависит, в каком направлении движутся данные по цепочке.
output [HBIT:0] out= is_input ? lower : higher;

//	Хранилище. Это все регистры, что есть в сортировщике
bit [HBIT:0] higher;
bit [HBIT:0] lower;

//	Здесь определяется, что будет в хранилище на следующем такте. 
//	В зависимости от направления движения данных, это будет 
//	либо higher и in_prev (lower выталкивается к хвосту), 
//	либо lower и in_next (higher выталкивается к голове)
wire [HBIT:0] cand_h= is_input ? higher : lower;
wire [HBIT:0] cand_l= is_input ? in_prev : in_next;

//	Далее описывается синхронная логика. 
//	В отличие от комбинационной схемы, от времени не зависещей,
//	в регистры можно писать только в определённые моменты.
always@(posedge clk )
if (~hold)
begin
	//	Здесь мы наконец сравниваем два числа-кандидата.
	higher <= ( cand_h >= cand_l ) ? cand_h : cand_l;
	lower  <= ( cand_h >= cand_l ) ? cand_l : cand_h;
end
endmodule

Всё.



Но я сделал ещё одну реализацию с таким же интерфейсом, но немного другими свойствами. Различия реализаций: Первая на основе цепочки сортирующих ячеек, вторая на основе двоичного дерева, в узлах которого такие же ячейки.
Первая реализация позволяет дописывать данные в частично опустошённый буфер (можно, например, сортировать запросы на прерывания по приоритету), древовидная после записи требует полного прочтения.
Преимущество древовидной реализации — в процессе работы двигается не вся цепочка, а только одна ветка — теоретически более энергоэффективно.

Древовидная реализация
использует рекурсию для описания двоичного дерева, я даже не ожидал, что это сработает на verilog-е. Приведу только образец рекурсивного определения дерева.

module NodeType (  );
endmodule

module TreeTemplate (  );
parameter TREE_LEVEL= 4;

NodeType node();	

generate
if ( TREE_LEVEL >0 )
begin
	TreeTemplate #( TREE_LEVEL-1 ) leftSubtree (  );
	TreeTemplate #( TREE_LEVEL-1 ) rightSubtree (  );
end
endgenerate

endmodule

Логика движения данных по дереву такая: при записи ветви выбираются поочерёдно. При чтении нужно сделать дополнительное сравнение, чтобы определить, в корне какого поддерева число больше. В результате дереву нужно больше компараторов по сравнению с цепочкой того же объёма. Преимущество дерева в том, что данные меньше движутся, а энергопотребление схемы сильно зависит от количества переключений состояния регистров.
Соответствующая картинка


Вообще-то, рекурсивные определения модулей это очень нехарактерный стиль для верилога. Должен признаться, данный проект — «паровоз для машиниста». Правильный подход таков, — задана цель написать сортировщик, мы выбираем реализацию — дерево. В моём же случае, сама идея написать сортировщик возникла из необходимости освоить работу с древовидными структурами, — для нужд вычислителя на базе комбинаторной логики. Я уже немного написал об этом проекте в конце своего предыдущего, первого на Хабре поста. Работа машины сводится к вычислению комбинаторного выражения методом параллельного переписывания термов. Основная идея — сопоставить дереву функциональной программы аппаратное дерево ячеек, способных применять комбинаторы. Теоретически, так можно эффективно решать задачи из булевой алгебры или исчисления предикатов, для целей символьных вычислений или доказательства теорем. Надеюсь, в ближайшие месяцы у меня будет готова работающая версия, способная редуцировать простенькие выражения. Если вам известны какие-нибудь практические задачи, хорошо ложащиеся на чистое лямбда исчисление или комбинаторную логику, напишите, пожалуйста, в комментариях.

Исходники модулей сортировщиков здесь под LGPL, есть тестовые проекты для плат Марсоход2, Terasic DE0 и DE2-115.

p.s. прошу прощения за пересоздание топика. Теперь я знаю, что нельзя убирать свежеопубликованный топик в черновики надолго в первые сутки.
@leshabirukov
карма
47,2
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (49)

  • +1
    Интересно. И какая получается максимальная частота выполнения 1 шага сортировки массивов скажем размеров 4, 16 и 256 элементов на DE0/D2-115?
    • 0
      У меня частота от размера массива не зависит, только от размера сравниваемого числа в битах: критический путь проходит через один компаратор(модуль сравнения чисел) для реализации цепочкой и через два компаратора для дерева. Я рассчитываю, что для упомянутых плат на частоте 100mhz (1280x1024 vga) можно сравнивать 64-битные слова для реализации цепочкой. Сейчас попробую переделать тестовый стенд чтобы проверить.
    • 0
      Не удалось заставить схему сбоить. Даже со 128-битными данными порядок у обоих реализаций, 256-битные Quartus отказывается компилировать, а повышать частоту сложно, и за железо немного боязно.
  • 0
    Интересно сравнение скорости выполнения сортировки «аппаратной» и «софтварной»
    • 0
      Аппаратная в данном случае работает 2*n тактов для n чисел, хорошая софтварная имеет сложность n*log(n), если одно сравнение будут делаться за один такт, то для массива из 256 чисел получим 2048 тактов против 512 у аппаратной. Ну и чем больше n тем лучше.
  • 0
    Мне кажется для сортировки чисел можно использовать и обычный процессор, но для поиска строк или применения regex'ов — вот тут как раз FPGA очень даже полезны.
    • 0
      Ну, программная сортировка ограничена алгоритмической сложностью. Что касается regex'ов, то это смотря какие regex-ы. Если нужен широкий канал наружу и простой обработчик (проверить на равенство чему-то, посчитать хэш), то обычный FPGA подход вероятно сработает. Но я ищу задачу где требуется нелинейный алгоритм с большим количеством переходов(проверить выполнимость булевой формулы), который не ложится на обычный обработчик сигналов.
      • +1
        Монте-карло симуляция карточной игры кажется подпадает под это определение.
        • 0
          Это как, задаём игровую ситуацию, делаем ход, а потом перебираем случайные продолжения? Как тренировочная задача может быть подойдёт.
          • 0
            Именно так. И поскольку некоторые ходы могут означать конец игры, а другие ее продолжение, получается нелинейная структура которую к сожалению GPU не очень охотно берет ввиду дивергенции ветвей, а вот на FPGA можно даже несколько реализаций процесса делать одновременно, если место позволяет.
  • +1
    <оффтоп, да не совсем>
    Интересно, когда появится оперативная память, стандартизированная под >90% десктоп и серверные архитектуры, способная самостоятельно выполнять различные операции над своими ячейками, поиск, копирование, сортировку,… произвольный код (по типу FPGA, даже и сильно ограниченный), к тому же многозадачно, параллельно и конечно же сверхэффективно как по энергопотреблению так и по скорости.
    </...>
    • 0
      Интеллектуальная память, реконфигурируемые вычисления получат развитие не раньше, чем появится адекватная модель их программирования. Я вот как раз хочу попробовать комбинаторную логику в такой роли.
      • 0
        Стоп, что значит «адекватная модель»? Просто нужен 4GL, вроде матлаба, проблема мне кажется не в этом.
        • 0
          Кстати сказать, MATLAB Simulink умеет генерить HDL. Но это всё compile time. А для run time нужен язык с естественными средствами метапрограммирования который мог бы, так сказать, себя на лету перекомпилировать. Тут по-моему у функциональных языков нет конкурентов.
          • 0
            Стоп, не понял, зачем на лету перекомпилировать? Вы предлагаете перепрошивать FPGA на разные задачи? Но ведь это ненулевое время, а для больших программ могут быть вообще секунды.
            • 0
              Не на разные задачи, а на разные варианты базовой задачи. У вас в карточной игре, я не знаю, вышла некоторая масть. Вы можете построить более совершенный расчётный алгоритм использующий этот факт. См. Суперкомпиляция.
              Секунды это специфика ПЛИС. Были бы алгоритмы, подразумевающие перестройку на лету, появились бы и средства переконфигурации.
              • 0
                Ну, если поменялась например козырная масть, это не сложно инкорпорировать в схему, а вот если поменялась сама игра — другое дело, придется перепрошивать все и вся.
              • 0
                Я думаю, если не решать задачу 'в лоб', делая полностью программируемой всю логику. Память внутри чипа делится на домены (сотни и тысячи), в каждом — свой, даже не процессор, а блок FPGA, имеющий прямой доступ к ячейкам памяти домена, этот блок минимальный, сотни ячеек (ну тысяча), достаточный чтобы описать просто логику работы с памятью и работу со структурами данных (та же сортировка, например, может быть определена на основе одного поля в структуре данных, которая в свою очередь может быть двусвязанным списком или деревом).

                в FPGA логика прошивается в свою собственную память, где конфигурация определяется той же побитовой матрицей (я верно понимаю что это почти та же флеш-память, где ячейки определяют связи между логическими элементами?), в нашем случае эти данные можно хранить в самой оперативной памяти, на этом можно неплохо сэкономить, ведь не полностью же все ячейки FPGA блоков нужны всегда, не нужные можно использовать как память общего назначения.
                • 0
                  Так, а чем это отличается от просто FPGA? И кстати, конфигурация FPGA во время работы хранится в ячейках статического ОЗУ, которые можно использовать альтернативно как дополнительную память. Флеш память непосредственно используется в другом типе ПЛИС — CPLD.
                  • 0
                    Значит я рад что ошибался (я думал что сам метод создания ячеек FPGA подразумевает технологию по типу FLASH памяти, со всеми вытекающими минусами), получается сам процесс прошивки FPGA модулей может не требовать какого-либо неприятно большого времени, а значит динамическая перепрошивка в процессе выполнения — вполне реальна. Вопросы компиляции 'на лету' можно отложить, это инженерные вопросы и решаемы так или иначе.

                    Просто FPGA от RAM отличаться будет тем что строение оперативной памяти уже давно не набор тригеров на базе логических элементов (так делают только что для кеш памяти процессора), а с целью плотности размещения на чипе и уменьшения энергопотребления используются технологии которые врят ли совместимы с технологиями FPGA матрицы. Т.е. на чипе придется совмещать их обе. Грубо говоря чем больше площади чипа мы отдадим FPGA тем меньше будет юзабельной памяти. А памяти мы хотим по прежнему много и подешевле.
                    • 0
                      … динамическая перепрошивка в процессе выполнения — вполне реальна. Вопросы компиляции 'на лету' можно отложить, это инженерные вопросы и решаемы так или иначе.

                      Так что прошивать то? Если у вас несколько готовых прошивок, которые надо менять время от времени, — такая технология уже есть. Для чего-то сложнее нужна перекомпиляция.
                      • 0
                        Да понятно, что все эти технологии есть… по отдельности, хотелось бы это уже в оперативной памяти, стандартной и для десктопа, с поддержкой процессоров и компиляторов :)

                        Дай возможность массам, а там и инструментарий наработается.
      • 0
        Ну полная универсальность пока наверное не актуальна… да елки палки, просто оперативная память с единственной распаралеливаемой инструкцией — копирование/перемещение, может дать такой мощный прирост, особенно с прямой поддержкой процессором, что тут эта область развиваться начнет.
        • +1
          Механизм копирования блока памяти без участия процессора давно существует — ПДП(DMA). А если копировать не блоком, то кто будет управлять процессом, ставить саму задачу?
          • 0
            Там речь о взаимодействии памяти и устройства без участия процессора. С работой внутри оперативной памяти оно справляется?
            • 0
              Да, канал ПДП из памяти в память тоже часто используется. Типичное применение — подкачка из объёмной внешней памяти в быструю внутреннюю.
          • +1
            DMA конечно процессор освобождает, но продолжает занимать шину данных, уже давно это бутылочное горлышко между процессором и памятью, и простая операция копирования занимает шину на 100%.
            • 0
              А что мешает расширять это горло? Можно ставить много независимых банков, можно использовать многопортовую память. Проблема в поддержании целостности системы в условиях массовой параллельной работы с памятью. Параллелизм надо поддерживать ещё на уровне парадигмы программирования, я ставлю на функциональный подход.
              • +1
                Ложкой черпать океан.
                Мы не можем достаточно расширить каналы передачи данных, к тому же это усложняет общую архитектуру компьютера. Развитие, как мне кажется, должно быть в добавлении собственных мозгов каждому компоненту, в данном случае — оперативной памяти.
  • +3
    А вы уверены, что это o(n)? n-то предполагается любого размера, а не фиксированного. Если мы говорим, что у нас размер фиксирован, то это вообще o(1).

    Если нам надо будет отсортировать M*n массив посредством этой штуки, где n — ёмкость этой штуки, то какой сложность будет относительно M?

    Подозреваю, что едва ли не o(M2).
    • 0
      Ну конечно, o(n) будет для n<n_max. Для случаев массивов больших n, польза всё равно будет, сортируем по кусочкам, а потом применяем сортировку слиянием. Должно по идее получиться o(n*(log(n/n_max)))
      • +1
        Это как вы так изящно деление под логарифм засунули? Получится o(n*log(n-n_max)) для сортировки слиянием блоков, помноженный на o(n_max) для сортировки плиской. n_max константа, так что ей можно пренебречь, получаем o(n*log(n)) — никакой разницы, «сортировка слиянием».

        Таким образом, алгоритмически ничего не поменялось. На практике поменялись константы — и это очень важно, на практике. Но с точки зрения чистой CS — тот же алгоритм, только переставляет за раз не 2, а const элементов.
        • 0
          Допустим n = 2*n_max. Отсортировали два куска n/2 аппаратно — n тактов (n/2+n/2). Слили два куска за n тактов. Итого 2*n
          Допустим n = 4*n_max. Отсортировали четыре куска n/4 аппаратно — n. Слили первый раз за n, стало два куска, слили второй раз за n Итого 3*n тактов.
          Допустим n = (2^k)*n_max. Отсортировали (2^k) куска n/(2^k) аппаратно — n. Слили первый раз за n, стало (2^(k-1)) куска, слили второй раз за n… Итого (k+1)*n тактов.
          (k+1) это как раз log(n/n_max).
          • +1
            В тот момент, когда вы говорите, что n= Cont1 * Const2, то у вас n становится константой, и сложность алгоритма становится o(1).

            Кстати, сортировка слиянием для n элементов всё равно o(n*log(n)), даже если куски отсортированы. Если у вас размер куска m, всего элементов n, то у вас n/m кусков, что есть o(n).
          • +1
            Вы прекрасный инженер, но плохо разбираетесь в теоретических основах компьютерных наук. О-нотация используется не для точной оценки количества операций, выполняемых в ходе алгоритма, а для оценки того, как хорошо алгоритм масштабируется.
            В вашем случае, масштабируемость не предусмотрена и вы всегда можете отсортировать n элементов за n тактов, при неизменном n. Это даже не О(n), это О(1) — т.е. алгоритм, в рамках своей реализации, всегда выполняет константное количество операций, равное n.
            О(1) означает, что ваш алгоритм пропорционален «f(x) = 1», с известным коэффициентом пропорциональности, равным n, вынесенным за О и отброшенным.
            Как только вы вводите масштабируемость, сортируя k > n элементов, с помощью слияния блоков, ваше О(1) сводится к слиянию k/n блоков, т.е. O(k*log(k)).
            • 0
              Ну хорошо, убедили, сейчас напишу дополнение. Хотя мне хотелось бы иметь возможность подчеркнуть тот факт, что моя сортировка быстрее программной, причём чем больше n (<n_max) тем больше выигрыш.
              • 0
                ну, вообще говоря, учитывая условие n<nmax, то и программная реализация O(n) существует. Например, в книге Кормена она есть, причём крайне простая. Вопрос лишь в выделении соответствующего массива памяти
                • 0
                  Цитата из Кормена:
                  … Разумеется, они улучшают оценку о(n log(n)) за счёт того, что используют не только попарные сравнения, но и внутреннюю структуру сортируемых объектов.

                  Мой модуль использует только попарные сравнения. Например, какие-нибудь double-ы сортировками семейства radix sort сортировать плохо.
  • +3
    Раз уж вы говорите, что за счет аппаратной реализации создали быстрый алгоритм, то стоило бы и сказать, сколько потратили ресурсов на эту реализацию.
    • +2
      Я не автор, но примерно скажу что время разработки на FPGA в 10-100 раз для простых проблем и 10-1000 для проблем промышленного масштаба. Более того, использование в реале несет нехилые косты в плане производства, и взаимодействие с классическими x86 системами это отдельная песня.

      Поэтому FPGA как механизм ускорения (а не контроля за LED-дисплеем на вокзале) окупается только в узком спектре дисциплин, например в финансовой инженерии.
      • +2
        Это тоже, безусловно, важно, но я имел в виду более приземленную вещь: аппаратные затраты (логика, триггеры и т.д.)
      • +1
        FPGA как механизм ускорения (а не контроля за LED-дисплеем на вокзале)

        Добавлю, что есть и другие важные области применения (такие как прототипирование ASIC и цифровая обработка сигналов в телекомуникационной отрасли), в которых использование FPGA не просто окупается, но ещё и едва ли не единственный применимый вариант.

        А по поводу времени разработки замечу, что вендоры на месте не сидят, а работают над решниями (OpenCL на FPGA, HDL coder для MATLAB).
        • +1
          Да вот как раз обработка сигналов это то узкое место где FPGA рулит. Например приходит к вам вагон данных с биржи, с которым x86 не справиться — делается FPGA feed handler который сам все распарсит и даже может назад что-то послать.
    • +2
      По трудозатратам я согласен с оценкой mezastel, а по ресурсам ПЛИС вот отчёт от Quartus для сортировщика с n_max=128, 16 битные числа:
      +--------------------------------------------------------------------------------------+
      ; Flow Summary                                                                         ;
      +------------------------------------+-------------------------------------------------+
      ; Flow Status                        ; Successful - Fri May 09 20:42:53 2014           ;
      ; Quartus II 32-bit Version          ; 13.0.1 Build 232 06/12/2013 SP 1 SJ Web Edition ;
      ; Revision Name                      ; DE0_VGA                                         ;
      ; Top-level Entity Name              ; DE0_VGA                                         ;
      ; Family                             ; Cyclone III                                     ;
      ; Device                             ; EP3C16F484C6                                    ;
      ; Timing Models                      ; Final                                           ;
      ; Total logic elements               ; 3,970 / 15,408 ( 26 % )                         ;
      ;     Total combinational functions  ; 3,732 / 15,408 ( 24 % )                         ;
      ;     Dedicated logic registers      ; 2,257 / 15,408 ( 15 % )                         ;
      ; Total registers                    ; 2257                                            ;
      ; Total pins                         ; 252 / 347 ( 73 % )                              ;
      ; Total virtual pins                 ; 0                                               ;
      ; Total memory bits                  ; 0 / 516,096 ( 0 % )                             ;
      ; Embedded Multiplier 9-bit elements ; 6 / 112 ( 5 % )                                 ;
      ; Total PLLs                         ; 1 / 4 ( 25 % )                                  ;
      +------------------------------------+-------------------------------------------------+
      • 0
        А можно сравнение для другого n_max? Интересно, линейная зависимость или какая.
        • +2
          Практически линейная, и для n_max и для разрядности.
          n_max=64, bits=16:
          ; Total logic elements               ; 2,317 / 15,408 ( 15 % )                         ;
          ;     Total combinational functions  ; 2,157 / 15,408 ( 14 % )                         ;
          ;     Dedicated logic registers      ; 1,233 / 15,408 ( 8 % )                          ;
          

          n_max=64, bits=32:
          ; Total logic elements               ; 4,567 / 15,408 ( 30 % )                         ;
          ;     Total combinational functions  ; 3,993 / 15,408 ( 26 % )                         ;
          ;     Dedicated logic registers      ; 2,369 / 15,408 ( 15 % )                         ;
          

  • 0
    в общем случае требует время O(n*log(n))

    Количество операций растёт с такой скоростью, а не время, тут вы лишь распараллеливаете.
    Попробуйте прикинуть сложность числа операций с ростом n вашем варианте.
  • 0
    Хорошо бы автор написал — сортировщик _каких_ чисел в данном случае реализован.
    Например — «целых положительных 8-битных».
    А то ализаровщина какая-то получается.
    • 0
      В данном случае, целых положительных с параметризованной разрядностью, но поскольку всё, кроме компаратора от типа данных не зависит, сравнивать можно что угодно, подобрав соответствующий компаратор. Можно числа с плавающей точкой, можно пары ключ-значение сортировать по ключу. Кстати, сортировка стабильная.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.