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.