Sort a large collection while showing progress

Question

What is the best way to sort a collection while updating a progress bar? Currently I have code like this:

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

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

This shows progress but the progress bar slows down as the number of items in sortedItems grows larger. Does anyone have a better approach? Ideally I'd like to use an interface similar to Collections.sort() so that I try different sorting algorithms.

Any help would be great!

---

As a bit of background, this code is pulling back lots of documents (1-10 million) from Lucene and running a custom comparator over them. Sorting them by writing data back onto the disk will be way too slow to be practical. Most of the cost is reading the item off the disk and then running the comparator over the items. My PC has loads of memory so there is no issues relating to swapping to disk, etc.

In the end I went with Stephen's solution since it was very clean and allowed me to easily add a multi-threaded sorting algorithm.

Answer 1

Why not implement your own merge sort (which is what Collections.sort is doing) and update the progress bar at key points of the algorithm (say, after each merge of more than 5% of the array)?