def mergeSort(array): if len(array) > 1: # r is the point where the array is divided into two subarrays r = len(array)//2 L = array[:r] M = array[r:] print(L,M) # Sort the two halves mergeSort(L) mergeSort(M) print(L,M) i = j = k = 0 # Until we reach either end of either L or M, pick larger among # elements L and M and place them in the correct position at A[p..r] while i < len(L) and j < len(M): if L[i] < M[j]: array[k] = L[i] i += 1 else: array[k] = M[j] j += 1 k += 1 # When we run out of elements in either L or M, # pick up the remaining elements and put in A[p..r] while i < len(L): array[k] = L[i] i += 1 k += 1 while j < len(M): array[k] = M[j] j += 1 k += 1 # Print the array def printList(array): for i in range(len(array)): print(array[i], end=" ") print() # Driver program if __name__ == '__main__': array = [6, 5, 12, 10, 9, 1] mergeSort(array) print("Sorted array is: ") printList(array)

O(n log(n))


    time complexity of the code:

    def printPairs(arr, arr_size, sum):
        s = set()
        for i in range(0, arr_size):
            temp = sum-arr[i]
            if (temp>=0 and temp in s):
                print ("Pair with the given sum is", arr[i], "and", temp)
            s.add(arr[i])

    # Driver program
    A = [1, 4, 45, 6, 10, -8]
    n = 16
    printPairs(A, len(A), n)


    O(n)