Consider an array containing N unique values where for some index i, the values are in increasingorder from index 0 to (i-1), and then again from i to (N-1). An example array is given below.Here i=3, it means the values are in increasing order from index 0 to 2, and then again from 3 to 7.index 0 1 2 3 4 5 6 7value 9 12 15 2 4 5 7 8Given the value of i, propose an algorithm to search a key_value in the array. Complexity of youralgorithm must be less than O(N).a) Present your solution idea as a code/ pseudocode/ flowchart/ step-by-step instructions/logical explanations in short.b) Write the time complexity of your presented solution.c) Show a simulation of the Merge Sort algorithm to organize the whole array in increasingorder.

a) The problem can be solved using a modified version of Binary Search. Here are the step-by-step instructions:

1. Start by dividing the array into two sub-arrays at index i. The first sub-array is from index 0 to (i-1) and the second sub-array is from i to (N-1).
2. Perform a binary search on both sub-arrays for the key_value.
3. If the key_value is found in either of the sub-arrays, return the index. If it's not found, return -1 or a message indicating that the key_value is not in the array.

Pseudocode:

function binarySearch(array, left, right, key_value)
    while left <= right
        mid = left + (right - left) / 2
        if array[mid] == key_value
            return mid
        else if array[mid] < key_value
            left = mid + 1
        else
            right = mid - 1
    return -1

function search(array, i, key_value)
    index1 = binarySearch(array, 0, i-1, key_value)
    index2 = binarySearch(array, i, N-1, key_value)
    if index1 != -1
        return index1
    else if index2 != -1
        return index2
    else
        return -1

b) The time complexity of the presented solution is O(log N) because we are performing a binary search on the two sub-arrays.

c) Here is a simulation of the Merge Sort algorithm:

1. Divide the unsorted list into N sublists, each containing one element (a list of one element is considered sorted).
2. Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. This will be the sorted list.

Pseudocode for Merge Sort:

function mergeSort(array)
    if length(array) > 1
        mid = length(array) / 2
        left = array[0, ..., mid-1]
        right = array[mid, ..., N-1]

        mergeSort(left)
        mergeSort(right)

        i = j = k = 0

        while i < length(left) and j < length(right)
            if left[i] < right[j]
                array[k] = left[i]
                i++
            else
                array[k] = right[j]
                j++
            k++

        while i < length(left)
            array[k] = left[i]
            i++
            k++

        while j < length(right)
            array[k] = right[j]
            j++
            k++

This will sort the entire array in increasing order.