What is the best sorting algorithm for an almost sorted array?

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.

Time complexity

The time complexity of an​ insertion sort is O(n)O(n) for almost sorted data.

svg viewer

Code

In the code below, we will compare the execution time for the merge sort and insertion sort of an almost sorted array.

We will be using the Python timeit module to compute the time for each algorithm​.

#Importing Library
import timeit
Insertion = '''
def insertion_sort():
arr = [1, 2, 4, 3]
for i in range(1, len(arr)):
# Set key:
key = arr[i]
j = i - 1
while 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) / 2
left = myList[:mid]
right = myList[mid:]
# Recursive call on each half
mergeSort(left)
mergeSort(right)
# Two iterators for traversing the two halves
i = 0
j = 0
# Iterator for the main list
k = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
# The value from the left half has been used
myList[k] = left[i]
# Move the iterator forward
i += 1
else:
myList[k] = right[j]
j += 1
# Move to the next slot
k += 1
# For all the remaining values
while i < len(left):
myList[k] = left[i]
i += 1
k += 1
while j < len(right):
myList[k]=right[j]
j += 1
k += 1
'''
print("Insertion sort:")
print(timeit.timeit(stmt=Insertion,number=10000000))
print("Merge sort:")
print(timeit.timeit(stmt=Merge,number=10000000))
New on Educative
Learn to Code
Learn any Language as a beginner
Develop a human edge in an AI powered world and learn to code with AI from our beginner friendly catalog
🎁 G i v e a w a y
30 Days of Code
Complete Educative’s daily coding challenge every day in September, and win exciting Prizes.

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved