Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

sorting
array
python

# What is the best sorting algorithm for an almost sorted array? Educative Answers Team

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

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. ## 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 Libraryimport timeitInsertion = '''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))

RELATED TAGS

sorting
array
python 