Suppose your operations on arrays were constrained as follows:
.get(i) accesses the element at index position 𝑖 in read-only mode.
.length() returns the length of the array.
.flip(i) flips the array up to index position 𝑖. Thus, the operation changes
{1,2,3,4}.flip(2) changes the array to {3,2,1,4}.
Only these three operations are available to you. Also assume that the three operations are in 𝑂(1).Develop an algorithm that sorts a given array in 𝑂(𝑛 × 𝑙𝑜𝑔 𝑛).To do this, proceed as follows:
Suppose you have an array of length 𝑖 + 1. You want to correctly sort the element at position 𝑖. The array is already sorted up to 𝑖 - 1. The correct position of the element at position 𝑖 is index position 𝑗. Find a sequence of flip operations that inserts the element in the correct location.
My problem is how to find the algorithm here?