algorithmsortingin-placecounting-sortstable-sort

Counting sort implementation that modifies the input array


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?


Solution

  • 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));