Consider a satellite moving around the earth along the equator and recording some data (air-pressure, temperature, height etc.) for scientific investigation. The data thus obtained is stored in a database where the key to each data entry is the longitude of the point. We require this data to be sorted, but each of the n data entries might have been misplaced by no more than k positions from the correct sorted order (k is a predefined constant, depending on the speed of the satellite). Design a worst-case time and space efficient algorithm for sorting such a dataset.