How one should optimally sort the almost sorted data of an array is a common problem. Many sorting algorithms are available, but the one which is best suited for the almost sorted array is the insertion sort.
The time complexity of an insertion sort is for almost sorted data.
In the code below, we will compare the execution time for the merge sort and insertion sort of an almost sorted array.
Learn more about insertion sort.
Learn more about merge sort.
We will be using the Python timeit module to compute the time for each algorithm.
#Importing Libraryimport timeitInsertion = '''def insertion_sort():arr = [1, 2, 4, 3]for i in range(1, len(arr)):# Set key:key = arr[i]j = i - 1while j >= 0 and arr[j] > key:# Swap:arr[j + 1] = arr[j]arr[j] = key# Decrement 'j':j -= 1'''Merge = '''def mergeSort():myList = [1, 2, 4, 3]if len(myList) > 1:mid = len(myList) / 2left = myList[:mid]right = myList[mid:]# Recursive call on each halfmergeSort(left)mergeSort(right)# Two iterators for traversing the two halvesi = 0j = 0# Iterator for the main listk = 0while i < len(left) and j < len(right):if left[i] < right[j]:# The value from the left half has been usedmyList[k] = left[i]# Move the iterator forwardi += 1else:myList[k] = right[j]j += 1# Move to the next slotk += 1# For all the remaining valueswhile i < len(left):myList[k] = left[i]i += 1k += 1while j < len(right):myList[k]=right[j]j += 1k += 1'''print("Insertion sort:")print(timeit.timeit(stmt=Insertion,number=10000000))print("Merge sort:")print(timeit.timeit(stmt=Merge,number=10000000))
Free Resources