Итак, в 1 МБ ~ 8 000 000 битов, но если у вас есть произвольные 7-значные числа (до 9 999 999), использование вектора битов для сортировки не будет работать. Точно так же это не будет работать, если некоторые числа могут повторяться, потому что вы можете хранить только {0,1} в битовом векторе.
Но, предположив (что, я думаю, ваша проблема задает), что у вас есть последовательность целых чисел от 0 до 8 000 000 без дубликатов, вы можете просто выделить обнуленный массив из 8 000 000 битов, а затем для каждого числа отметить соответствующую бит в массиве. Затем вывод отсортированного списка - это просто последовательное чтение этого массива и вывод индекса для каждого значения 1.
Если вы задаете более сложную версию вопроса (0–10 миллионов, повторы разрешены), то вам нужно будет отсортировать куски, подходящие для оперативной памяти, сохранить их на диске, а затем объединить эти куски в линейное время и потоковая передача (так что вам никогда не придется хранить все это в памяти). Вот реализация очень похожей вещи в Python: http://neopythonic.blogspot.com/2008/10/sorting-million-32-bit-integers-in-2mb.html