Сортировка большой коллекции с отображением хода выполнения

Как лучше всего отсортировать коллекцию при обновлении индикатора выполнения? В настоящее время у меня есть такой код:

for (int i = 0; i < items.size(); i++)
{
    progressBar.setValue(i);

    // Uses Collections.binarySearch:
    CollectionUtils.insertInOrder(sortedItems, item.get(i));
}

Это показывает прогресс, но индикатор выполнения замедляется по мере увеличения количества элементов в sortedItems . У кого-нибудь есть подход лучше? В идеале я хотел бы использовать интерфейс, похожий на Collections.sort () , чтобы я пробовал разные алгоритмы сортировки.

Любая помощь была бы замечательной!

В качестве фона, этот код забирает множество документов (1-10 миллионов) из Lucene и запускает над ними специальный компаратор. Сортировка их путем записи данных обратно на диск будет слишком медленной, чтобы быть практичной. Большая часть затрат связана с чтением элемента с диска и последующим запуском компаратора по элементам. На моем компьютере много памяти, поэтому нет проблем, связанных с переключением на диск и т. Д.

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