How to sort a specific kind of input

Question

I have a sequence of elements, say a1,a2,...,an. (n ~ 4*10^7)

The input will be mostly sorted. More specifically any element less than a_i will be either to the left, or very close to the right(~ 300 elements).

How can I sort this sequence efficiently?

Solution

You could do this using a heap of N elements where N is the maximum overlap (N=300 in your case).

Start with an empty heap.

For each element in the sequence:

1. Add element to the heap

2. If the heap has more than N elements, output (and remove from the heap) the smallest element

Finally output the remaining elements in the heap.

This will have complexity O(nlogN)

Comments

[mmgp]

Check natural mergesort.

[Yrogirg]

how do I configure it to disable showing running applications?

[aroque]

I don't know. Try asking in the extension page.

[Bogdan]

I would say to use a queue/list of size N and always keep it sorted by inserting each new element at its correct location. When the size reaches N start removing the smallest elements.