Поразрядная сортировка разделением

13 6 11 15 8 14 Исходный
1101 0110 1011 1111 1000 1110 массив
-- ------------------------ Разделение
6 15 13 11 8 14 по биту 3
-- --------- --------- Разделение
6 11 8 15 13 14 по биту 2
-- -- -- -- --------- Разделение
6 8 11 13 15 14 по биту 1
-- -- -- -- -- -- Разделение
6 8 11 13 14 15 по биту 0

В нашем примере после выполнения разделения по 3-у биту массив делится на две части, границей которых является значение 8. Затем обе части делятся пополам со значениями границ, определяемых 2-м битом, т.е. 4 и 12 и т.д..

void bitsort(int A[],int a,int b, unsigned m)
{
int i;
if (a+1 &#62= b) return; // Интервал сжался в точку

if (m == 0) return; // Проверяемые биты закончились

// Маска после сдвига стала 0

// Разделить массив на две части по значению бита,

// установленного в m, i - граница разделенных частей

bitsort(A,a,i,m &#62&#62 1);
bitsort(A,i+1,b,m &#62&#62 1);
}

Приведенная функция выполняет поразрядную сортировку части массива A, ограниченного индексами a и b. Этот интервал разделяется на две части (интервалы a..i, i+1..b), в которые попадают значения элементов массива соответственно с нулевым и единичным значением проверяемого бита. Сам бит задается маской m -переменной, в котором его значение установлено в 1. Затем функция вызывает самое себя для обработки полученных частей, для которых выполняется разделение по следующему правому биту. Для этого текущая маска m сдвигается на 1 разряд вправо. Вызов функцией самой себя называется рекурсией (см.5.4).