Question

Write a program to sort a list of integers using Insertion sort, Mergesort and Quicksort. First take as input the size ‘n’ of the array, then read in the ‘n’ input integers that need to be sorted.

Answer 1

def insertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr


def mergeSort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]
        mergeSort(L)
        mergeSort(R)
        i = j = k = 0
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1
        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1
    return arr


def quickSort(arr):
    less = []
    equal = []
    greater = []
    if len(arr) > 1:
        pivot = arr[0]
        for x in arr:
            if x < pivot:
                less.append(x)
            elif x == pivot:
                equal.append(x)
            elif x > pivot:
                greater.append(x)
        return quickSort(less)+equal+quickSort(greater)
    else:
        return arr


def main():
    arr = [int(x) for x in input().split()]
    print('Insertion sort: ', insertionSort(arr))
    print('Merge sort: ', mergeSort(arr))
    print('Quick sort: ', quickSort(arr))


if __name__ == '__main__':
    main()