how to sort an array which is mostly sorted

Question

i have an array like this:
1,2,3,5,6,4 it is 99% sorted and has 40K elements.
i can put them in an array, list, linked list, ...
but i don`t know the fastest way to sort them!

Answer 1

Google gives a lot of results for this, e.g. this one with an overview of various methods how to accomplish that: http://home.tiac.net/~cri/2004/ksort.html

Answer 2

The following site has a comparison between common sorting algorithms - it seems that insertion sort wins when the collection is nearly sorted.

Answer 3

If it's already ordered to such a high degree, and the not-quite-sorted elements are not far from their correct positions, then this may be one of the few cases that bubblesort is useful.

Answer 4

"They laughed when I sat down at the keyboard and coded a bubblesort..."

But seriously: Bubblesort is close but not quite. Bubblesort repeatedly moves in one direction, so if there's a low-key value near the top end of the array it and the comparison site "bubbles" upward all the time, it takes many iterations of the main loop for the data item to bubble down against the current. That's pretty much worst case behavior, which for Bubblesort is disastrous.

But there's a refinement to BubbleSort, sometimes called ElevatorCocktail Sort, where the bubble moves in alternating directions: One pass up, one pass down, repeat. This permits single elements to move a long distance in a single pass (or actually, 2 passes), and the number of passes is proportional to the number of elements that need moving. For a small number of unsorted elements, this can approach efficiency.

---

I believe that for the general case, the second link in marek's answer will be faster. The advantage of Bubble/ElevatorCocktail sort is that it's so simple, it's virtually foolproof, and not a lot of work.

Answer 5

As with most questions of this sort, the answer is "That depends...". Do you care if the sort is stable, i.e. if elements whose keys are equal retain their original relative ordering after being sorted? Do you just care about raw speed? Is simplicity of implementation important? Does memory consumption matter?

Personally, I will always choose a stable sort algorithm, as I'm willing to sacrifice some raw speed for what I consider to be "reasonable" behavior, and non-stable sorting is too often "unreasonable". So I tend to go with the merge-sort algorithm, which is fast and reasonably simple, but it does use extra memory. Another advantage of merge-sort is that if the data is already sorted its complexity is O(n), so for nearly-sorted data it should be close to O(n).

YMMV.

Answer 6

Is performance critical (as verified by a profiler)? Otherwise, just use your framework/langauge's default sort (probably quicksort). It will perform decently.