Hi. Today I got an exam on "Algorithms and data structures" for people which learnt sorting month ago and there was a problem that neither me nor Marcin_smu and few other good guys didn't solve and I'm interested in a solution, so maybe you can help?
We are given an array of integers a[1..n] and an integer k ≤ n1 / 2 such that at least k different values are present in a. We need to swap some elements so that first k elements are pairwise different, they are sorted in increasing order and everything is changed in a stable way, which means that for a fixed value our changes preserved order among elements within that value. Moreover everything needs to be done inplace, that means we can use at most constant additional memory. Whole algorithms has to run in 
.
Maybe the following would work? (quite a few details, so might be broken...)
Scan A[1..n] from left to right. After having processed the first i elements, the invariant is that A[1..i] is partitioned into three parts: the left junkyard, the buffer, and the right junkyard, so that:
Now, take the next A[i+1]. Binary search in the buffer to figure out if A[i+1] appears there. If so, swap it with the equal element in the buffer to maintain 3). If A[i+1] is a new element, we swap the buffer and the right junkyard (to transform AB into BA, notice that we can reverse a subarray in linear time, so we can compute (A^R B^R)^R = BA). Then the right junkyard becomes empty, and we can extend the buffer with the new element A[i+1] (this requires inserting it into the appropriate place there, which is kind of slow). If the buffer contains b elements, and the right junkyard stores s elements, the complexity is O(b+s). Because the right junkyard becomes empty, paying O(s) is OK. Paying O(b) is not that OK, but notice that this happens only when we extend the buffer, which happens just k times, so all in all we pay O(n) for moving things around, plus O(nlogn) for the binary searching. In the end the buffer is somewhere in the middle of the array, so we move it to to front (again with reversals).
That idea seems very to be really elegant to me, but if I'm not mistaken in the end when swapping buffer and left junkyard we lose stability. But I think that we can fix this by changing a little our invariants. We change in 3) invariant swapping buffer and right junkyard with swapping buffer and left junkyard and we are not doing anything when we find out that A[i+1] is present in buffer. One little issue more is that we should remember to end our algorithm when buffer's size reaches k, because we can have n different values :P. Is that correct now?
Oops, you're right, the last step destroys the stability. I think that your fix works!
I think I know how to solve this, but using complicated http://en.wikipedia.org/wiki/Block_sort algorithm. It sorts in-place and preserves stability! So for start we execute block sort on our sequence. Assuming that our sequence is sorted we can proceed using sliding window algorithm. We go from right to left and collect a buffer of distinct elements. After processing elements a[n], ..., a[i] we want a[i], ..., a[i + len — 1] to be our buffer and a[i + len], ..., a[n] to be all other elements with preserved order. Whenever we encounter an element that is first from left with that value we add it to our buffer which corresponds to just extending size of our buffer by 1. In other case we swap that element with last element of our buffer. In the end we sort inplace our buffer.
Sliding window algorithm is implemented here: http://ideone.com/2jAZxY
Advantage of that algorithm is that its complexity doesn't depend on k!