Sorting algorithm for almost sorted data?

[TriKri]

Hello!

I would like to find a good sorting algorithm for sorting data that already is almost sorted. That means, an elemend is at a possition in the array that usually isn't very far from where it is going to end up, so say you are sorting like 1,000,000 numbers, and all of the numbers has an index that differs at the most 10 from the index it is going to get when it has been sorted... Is there some fast sorting algorithm for doing this?

[STLDude]

A while back I had the similar requirement and used this resource (http://home.tiac.net/~cri/2004/ksort.html).

[TriKri]

The limit of 10 I am not sure of, it is just like a possible standard derivation. But I think I have found a way to do it with merge sort (then not moving all the elements being merged to another array). I still haven't read the page you linked me to yet, but thanks for it! I will read it through!