Algorithm to generate a 'nearly sorted' or 'k sorted' list?

Question

I want to generate some test data to test a function that merges 'k sorted' lists (lists where each element is at most k positions away from it's correct sorted position) into a single fully sorted list. I have an approach that works but I'm not sure how well randomized it is and I feel there should be a simpler / more elegant way to do this. My current approach:

1. Generate n random elements paired with an integer index.
2. Sort random elements.
3. Set paired index for each element to its sorted position.
4. Work backwards through the elements, swapping each element with an element a random distance between 1 and k positions behind it in the list. Only swap with the target element if its paired index is its current index (this avoids swapping an element that is already out of place and moving it further than k positions away from where it should be).
5. Copy the perturbed elements out into another list.

Like I say, this works but I'm interested in alternative / better approaches.

Answer 1

I think you could just fill an array with random integers and then run quicksort on it with a custom stopping condition.

If in a particular quicksort recursion your start and end indexes are less than k apart, then just return instead of continuing to recur.

Because of how quicksort works, every number in the start..end interval belongs somewhere in that region; worst case is that array[start] might really belong at array[end] (or vice versa) in truly sorted order. So, assuring that start and end are no more than k apart should be sufficient.