How to sort an array that is basically sorted

Question

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

Answer 1

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

Answer 2

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

But seriously: Bubblesort is close, but not quite. Bubblesort repeatedly moves in the same direction, therefore, if there is a small value near the upper end of the array, and the comparison site “bubbles up” all the time, many iterations of the main loop are required for the data element to go downstream. This is a very worst behavior that is disastrous for Bubblesort.

But there is a clarification for BubbleSort, sometimes called the Elevator Cocktail Sort, where the bubble moves in alternating directions: one skip, one pass down, repeat. This allows individual elements to move long distances in one pass (or, in fact, 2 passes), and the number of passes is proportional to the number of elements that need to be moved. For a small amount of unsorted items, this may come close to efficiency.

---

I believe that for the general case, the second link in the answer will be faster. The advantage of Bubble / Elevator Cocktail sorting is that it is so simple, it is almost flawless, and not much work.

Answer 3

If it is already ordered to such a high degree, and not quite ordered elements are close to their right positions, this may be one of the few cases where bubblesort is useful.

Answer 4

Google provides many results for this, for example. This is one with an overview of the various methods for doing this: http://home.tiac.net/~cri/2004/ksort.html

Answer 5

Put them in an array. You do not want to contact a 40k linked list.

There is a very narrow case for CocktailSort (bubblesort in two directions). But it depends on what exactly 1% of unsorted funds means. If there are several elements moved, but close to their target positions, this may work.

But InsertionSort or ShellSort will almost always win. Even when CocktailSort is theoretically better, the difference will be small. Thus, they are (much) safer bets.

Answer 6

As with most questions of this kind, the answer is "It depends ...". You are not interested in whether the type is stable, i.e. If the elements whose keys are equal retain their original relative ordering after sorting? You just care about speed? Is implementation importance important? Does memory consumption matter?

Personally, I will always choose a stable sorting algorithm, since I am ready to sacrifice some initial speed for what I consider “reasonable”, and unstable sorting is too often “unreasonable”. Therefore, I tend to go with a merge sorting algorithm, which is fast and fairly simple, but it uses extra memory. Another advantage of the merge-sort method 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 7

Is performance critical (as verified by the profiler)? Otherwise, just use your default / langauge view by default (probably quicksort). He will act decently.