sort algorithms for mostly sorted list [duplicate]

Question

This question already has answers here:

Which sort algorithm works best on mostly sorted data? [closed] (20 answers)

Closed 8 years ago.

I am working on a list of integers from a file. And I have to use a sorting algorithm to categorize them in descending order. I am familiar with the run time of a few sorting algorithms and I know the use of them is situational. So my question is: What would be the quickest sorting algorithm for a list of ANY size that is already 90% sorted? (in my file I have 10.000 entries but 9.500 of them are already sorted).

Thank you,

Answer 1

Insertion sort should be fine, if you choose to code it yourself rather than using the language provided sort functions.

1. It performs really well when the list is almost sorted (Though it is of Order O(N^2), if the list is almost sorted, the inner loop will not be executed often)
2. It is pretty easy to implement.

Presenting the Python implementation of Insertion Sort.

Program

def InsertionSort(Array):
    Total = 0
    for i in xrange(1, len(Array)):
        j, I, = i - 1, i
        while j >= 0 and Array[I] > Array[j]:
            Array[I], Array[j] = Array[j], Array[I]
            j, I, Total = j - 1, I - 1, Total + 1
    print "Insertion Sort Total Operations :", Total

Output

Worstcase

TestArray  = range(1, 11)
InsertionSort(TestArray)
Insertion Sort Total Operations : 45

Bestcase

TestArray  = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
InsertionSort(TestArray)
Insertion Sort Total Operations : 0

90% Sorted Array

TestArray  = [1, 9, 8, 7, 6, 5, 4, 3, 2, 10]
InsertionSort(TestArray)
Insertion Sort Total Operations : 17

Half Sorted Array

TestArray  = [10, 9, 8, 7, 6, 1, 2, 3, 4, 5]
InsertionSort(TestArray)
Insertion Sort Total Operations : 10

Answer 2

The Timsort algorithm as developed for Python, (and now used in Java), has optimisations to deal with partially sorted "runs" built in.

Answer 3

For its std::sort C++ uses introspective sort, where the array/list is first sorted using quicksort for a certain depth of recursion followed by heapsort. I dunno about 90% but heapsort seems to perform well on already sorted arrays/lists... so I'd recommend you try that.