Counting sort implementation that modifies the input array

Question

On the Wikipedia page about Counting Sort, it states:

It is possible to modify the algorithm so that it places the items into sorted order within the same array that was given to it as the input, using only the count array as auxiliary storage; however, the modified in-place version of counting sort is not stable.

I am curious about how such algorithm is implemented, but I don't have access to the source cited. Could somebody explain how it works?

Answer 1

After counting, you have an array of counts for each value, say:

[4,3,1,2]

Shift it to the right:

[0,4,3,1]

With a cumulative sum, change this into an array of the start positions for each value in the sorted result:

[0,4,7,8]

Now you walk through the array, swapping each each item into place at the start position for its value, and incrementing the start position so the next one will go in the right place, but ONLY if the item belongs the same or earlier position. If it belongs in a later position, then just skip it, and the item that belongs there will be swapped in when we get to it (because it must belong in the earlier position).

Swapping will bring a new element into the target position, so repeat at the same position until you find one that isn't swapped.

Here's the algorithm in JavaScript, using values from 0 to 9:

const len = 25;
const array = [];
for (let i=0; i<len; ++i) {
    array.push(Math.floor(Math.random()*10));
}
console.log("Original array:", String(array));

const cp = [0,0,0,0,0,0,0,0,0,0];
for (const val of array) {
  ++cp[val];
}
console.log("Counts:", String(cp));

for (let i=cp.length-1; i>0; --i) {
  cp[i] = cp[i-1];
}
cp[0]=0;
for (let i=1; i<cp.length; ++i) {
  cp[i]+=cp[i-1];
}
console.log("Start pointers: ", String(cp));

let pos=0;
while(pos < array.length) {
  let v = array[pos];
  let dest = cp[v];
  if (dest <= pos) {
    if (dest < pos) {
      // v belongs at an earlier position. Swap it into place
      array[pos] = array[dest];
      array[dest] = v;
    } else {
      // v belongs at the same position. don't visit it again
      ++pos;
    }
    // increment the pointer for this value
    cp[v] = dest+1;
  } else {
    // v belongs at a later position.  Something later must belong here.
    // Skip it and let the later item swap in when we get there
    ++pos;
  }
}

console.log("Sorted array:", String(array));

Answer 2

Totally untested C++ code

#include <array>
#include <vector>
#include <algorithm>
#include <numeric>

void counting_sort(std::vector<uint8_t>& values) {
    std::array<uint8_t , 256> count;

    for(auto& value : values)
        count[value]++; // count

    std::partial_sum(count.begin(), count.end(), count.begin()); // sum

    std::array<uint8_t , 256> position;

    position[0] = 0; // first position of first value
    std::copy_n(count.begin(), count.size()-1, std::next(position.begin())); // moved by one

    int pos = 0;

    while (pos < count.size()) {
        while (count[pos] > position[pos]) {
            auto& from = position[pos]; // current position
            auto& to = position[values[from]]; // final position
            if (to != from)
              std::swap(values[from], // from current position
                        values[to]);  // where the value needs to go
            to++; // update destination position
        }
        pos++;   
    }
}

In the while with the swap you keep swapping until the value that should be place in the first position is swapped into that position.

0 // pos
[3,2,1] // values
[0,1,1,1] // count
[_0_,1,2,3] // count
[_0_,0,1,2] // position
1 // pos
[0,_1_,2,3] // count
[0,_0_,1,2] // position

values[position[pos]] -> 3
position[3] -> 2
position[pos] -> 0
[_3_,2,_1_]
swap
[1,2,3]
position[values[pos]]++
[0,0,1,_2_] // position
[0,0,1,_3_] // position

1 // pos
[0,_1_,2,3] // count
[0,_0_,1,3] // position

values[position[pos]] -> 1
position[1] -> 0
position[pos] -> 0

positions are the same so update to
[0,_0_,1,3] // position
[0,_1_,1,3] // position

[0,_1_,2,3] // count
[0,_1_,1,3] // position
update pos
pos = 2
[0,1,_2_,3] // count
[0,1,_1_,3] // position
positions are the same to update to
[0,1,_1_,3] // position
[0,1,_2_,3] // position

count&position are the same so update pos
pos = 3
count&position are the same so update pos
pos = 4
done