I encounter a interesting algorithms: we have a sorted integer array arr, but someone inserted some integers (very small number of integers) into the arr. how to sort the new arr.
Right now my idea is to get all the index of the inserted integers, and store and sort them, then merge. but the tricky part is we don't know the original array, and just have the new arr, it is not easy to find out the indexes of inserted integers.
any idea?