/*
In-place Histogram Sort
by Marion McCoskey
December 11, 1998
*/

//          12345678901234567
char buf[]="ABEDEBEDDBEBDBDEB";//buffer with data to sort

void main(){

    unsigned hstS[5];   //sort histogram
    unsigned hstR[5];   //reference histogram
    unsigned ind;       //index variable
    char tmp0;          //first temporary storage
    char tmp1;          //second temporary storage
    unsigned pnt;       //pointer
    unsigned ePnt;      //empty pointer, points to a region with an empty
					    // storage element
    unsigned siz=sizeof(buf)-1;//size of the sort buffer minus the zero
                        // termination

    for(ind=0;ind<5;ind++)  //Clear the sort histogram.
        hstS[ind]=0;

    for(ind=0;ind<siz;ind++)//Fill in the sort histogram

		hstS[buf[ind]-'A']++;// with counts of data items in the sort
							 // buffer.

        tmp0=0;
        for(ind=0;ind<5;ind++){ //Integrate the sort histogram
                                // and copy to the reference histogram.
            tmp1=hstS[ind];
            hstS[ind]=hstR[ind]=tmp0;
            tmp0+=tmp1;
    }

    ind=0;                  //Find the first region
    while(!hstS[ind++]);    // with one or more data items.
    ePnt=ind-2;             //Store the selected region in the empty pointer.
    tmp0=buf[hstS[ePnt]];   //Read the first item from the selected region
                            // into temporary storage.

    for(ind=0;ind<siz;ind++){//Do the actual sort.

        pnt=tmp0-'A';   //Convert the data item in first temporary storage
                        // into a data pointer.
        if(pnt==ePnt){  //Does this region have an empty buffer location?

            //Region has an empty buffer location

            buf[hstS[ePnt]++]=tmp0; //Put the item in first temporary storage
                                    //  into the empty buffer location.

            while(hstS[ePnt]==hstR[ePnt+1]) //Find the next unsorted item
                                            //in the buffer.
                ePnt++; //All items in the tested region have been sorted.
                        //Increment the empty pointer and try the next region.
                tmp0=buf[hstS[ePnt]];   //Move the unsorted data item to first temporary storage.
            }
        else{

            //Region does not have an empty buffer location.

            tmp1=buf[hstS[pnt]];//Put the item pointed to by the histogram entry
                // for this region into second temporary storage.
            buf[hstS[pnt]++]=tmp0;//Store the data item from first temporary storage
                // into its sorted location in the sort buffer.
            tmp0=tmp1;//Move the data item from first temporary storage
                // to second temporary storage.

        }
    }
}