In cloud computing, it is common for a client, $$Alice$,$ to store her data on an external server owned by a cloud storage provider, $$Bob$.$ Because Bob is likely to be honest, but curious, Alice wants to keep the contents of her data private from Bob. Of course, she can encrypt her data using a secret key that only she knows, but that is not enough, since she may reveal information about her data simply based on the pattern in which she accesses her data. Since Bob can see the access pattern for Alice$$s data, even if she encrypts it$,$ Alice should consider using an algorithm that has a data access pattern that does not depend on any of its input values. Such an algorithm is said to be data$-$oblivious. Suppose, then, that Alice wants to sort an array, A$,$ of elements stored on Bob$$s computer, but do so in a data$-$oblivious fashion, so that she sorts privately, even though each time she accesses some item, A$[$i$],$ in the array, A$,$ Bob learns that she is accessing the item at index i$.$ She can use a constant amount of local private memory, e$.$g$.,$ to store indices, pointers, or to perform a comparison and swap, if the elements