How to efficiently *nearly* sort a list?

Question

I have a list of items; I want to sort them, but I want a small element of randomness so they are not strictly in order, only on average ordered.

How can I do this most efficiently?

I don't mind if the quality of the random is not especially good, e.g. it simply based on the chance ordering of the input, e.g. an early-terminated incomplete sort.

_{The context is implementing a nearly-greedy search by introducing a very slight element of inexactness; this is in a tight loop and so the speed of sorting and calling random() are to be considered}

My current code is to do a std::sort (this being C++) and then do a very short shuffle just in the early part of the array:

for(int i=0; i<3; i++) // I know I have more than 6 elements
    std::swap(order[i],order[i+rand()%3]);

Answer 1

Use first two passes of JSort. Build heap twice, but do not perform insertion sort. If element of randomness is not small enough, repeat.

---

There is an approach that (unlike incomplete JSort) allows finer control over the resulting randomness and has time complexity dependent on randomness (the more random result is needed, the less time complexity). Use heapsort with Soft heap. For detailed description of the soft heap, see pdf 1 or pdf 2.