sort array without conditional

Question

I need a program that sorts an array of integers without using conditional statements. Numbers are in the range from 0 to 100 and don't repeat.

#include <iostream>
using namespace std;

int main() {
    int arr[] = { 34, 12, 24, 65, 63, 22 };
    int arraySize = (sizeof(arr) / sizeof(*arr));
    unsigned char buf[101] = { 0 };

    for (int k = 0; k < arraySize; k++) {
        buf[arr[k]]++;
    }

    unsigned char i = 0;
    for (int k = 0; k <= 100; k++) {
        arr[i] = k;
        i += buf[k];
    }

    for (int a : arr) {
        cout << a << endl;
    }
    system("pause");
    return 0;
}

This program works but I get the error after closing of the command prompt:

Run-Time Check Failure #2 - Stack around the variable 'arr' was corrupted.

Is there a way to fix it?

Answer 1

The problem is that your code writes past the end of the array. It happens after you have encountered the last element in the counted sequence, but before the array buf has been exhausted, i.e.

for (int k = 0; k <= 100; k++) {
    arr[i] = k;
    i += buf[k];
}

When you add the highest element, which is 65, to the result, i reaches 6, so assigning a[i] becomes illegal. See what's going on by adding an extra element to your array, setting it to -1, and watching what happens to it (it gets set to 100; demo 1).

You can fix it by adding an early exit condition to stop as soon as you filled the array back, i.e.

for (int k = 0; i < arraySize && k <= 100; k++) {
    arr[i] = k;
    i += buf[k];
}

Now the -1 past the end of "active" part of our array remains -1 (demo).