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)$ for almost sorted data.

#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))

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

Time complexity

Code