Question

Lets say that I were to give you a sorted list of P elements that was followed by randomly ordered elements. Please explain how you would sort the entire, whole list? Please give a detailed reasoning and provide a good explanation (In language C++)

Please type answer if you can

Answer 1

I will use the below function

int sortedIndex(int array[],int value) {
    int low = 0,high = sizeof(array)/sizeof(array[0]);;

    while (low < high) {
        int mid = (low + high) >> 1;
        if (array[mid] < value) low = mid + 1;
        else high = mid;
    }
    return low;
}

Explanation

As intially P elements are sorted so i will pass array from 0 to P elements and the P+1 element to my function, now what the function does is relate to binary search , we are given sorted array and an element which we need to insert to array so that the resulting array is also sorted.

To find the position we divide the array and find mid and then compare mid with the element and until we find the right place of element we keep on doing this(hope you know binary search). Now we return the index, now in main function as we got the index where we need to insert it we insert it there and shift each element. Now again do this your new P is P+1 array and next element is P+2, keep on doing until you reach last element.