OberonCore

Рестартуйте ББ. С чистого листа 1.2 гига непрерывного пространства он найдёт со значительно большей вероятностью. Но сделать это повторно сможет едва ли.

Мой тест не работает через раз, иногда он все-таки выделяет 1,2 Гбайта.

Видимо придется сделать, что-то типа списка или дерева, раз большие массивы не всегда выделяются.

Советую ознакомиться с "Алгоритмами и структурами данных" Вирта. Глава 2.4. про сортировку последовательностей. На мой взгляд, материал отвечает требованиям задачи.

Добавлю ещё. Держать в памяти все 3.0е7 записей в памяти мне кажется неразумным решением. Полагаю, нужна БД. Пусть SQLite или RRD tool (если история). Создай индексы и производи себе нужные выборки. Зачем велосипед изобретать?
А за чрезмерное потребление памяти пора ввести систему штрафов.
Сортировать массив заново после каждого добавления мне кажется диким методом. А если есть мат. зависимость между числами, то и подавно.

Не могу согласиться с последним высказыванием. Во-первых, есть знаменитая дилемма память - скорость. Мы можем сэкономить память, но потеряем в скорости, или же мы можем выиграть в скорости, но будем использовать больше памяти. И каждый уже сам выбирает что важнее память или скорость. Лично для меня скорость важнее.
Во-вторых, использовать БД, там где она не нужна, считаю не разумным в квадрате. К одной из книг видел, таблицу, где приводиться порядок времени для обращения к оперативной памяти, файлу или базе данных. Так вот, считывание из файла на порядок или на два порядка медленнее, чем считывать из памяти, а делать выборку из базы данных еще примерно на порядок медленнее, чем считывать из файла.
В-третьих, база данных тоже использует оперативную память. И возможно, что программа и база данных будут вместе требовать больше памяти, чем только программа.

Можно не соглашаться со мной, однако,

1. Использование памяти должно быть с умом, так как размер 2ГБ не является столь распространённым среди ПК. И не факт , что система сможет себе позволить отдать кусок памяти размером более 1.2 ГБ.
   Не стоит также забывать, что перерасход памяти ведёт к интенсивному использованию файла/раздела подкачки системой, что резко снизит её производительность вместе с программой.
2. В БД используются различные техники оптимизации расхода памяти и быстродействия, использующие особенности систем, могущие оказаться гораздо эффективнее многочисленных сортировок с переразмещениями данных в памяти твоей программы по скорости и объёму потребляемой памяти. Создание индексов нужных полей позволит находить нужные записи одним запросом.
   Во всяком случае, не стоит отказывать себе в проверке БД на деле, особенно, если данные используются на продолжительный срок. Кроме того, SQLite, к примеру, позволяет держать данные полностью в памяти, если это так нужно (плюс она ещё и бесплатна).

Насчёт природы происхождения данных - ничего не было сказано. Будем считать, что данные случайны. Если это не так, то стоит перерассматривать дизайн программы.