Memory-Adjustable Navigation Piles with Applications to Sorting and Convex Hulls

Omar Darwish, Amr Elmasry, Jyrki Katajainen

We consider space-bounded computations on a random-access machine (RAM) where the input is given on a read-only random-access medium, the output is to be produced to a write-only s…