algorithm - Counting sort in C implemented according to pseudocode but doesn't run properly -

i have implemented counting sort according pseudocode ( that's written on blackboard in video explanation ) mysterious reason, doesn't seem sort properly.

for test input: 10 9 8 7 6 5 4 3 2 1

it gives: 3 4 5 6 7 8 1 0 0 9

it seems simple problem can't figure out why happening.

void counting(int * array, int n){      int *copy, *out, i,j, max, counter;      copy = (int*) malloc(sizeof(int) * max);      out = (int*) malloc(sizeof(int) * n );      max = array[0];      // finds max size     for(i=0;i<n;++i) if(array[i] > max) max = array[i];      // zeroes counting array     for(i=0;i<max;++i) copy[i] = 0;      //counts     for(i=0;i<n;++i) ++copy[array[i]];      //cumulative sum     for(i=1;i<max;++i) copy[i] += copy[i-1];      //sorts     for(i=n-1;i>=1;--i){         out[copy[array[i]]] = array[i];         --copy[array[i]];     }      //overwrite original array sorted output     for(i=0;i<n;++i) array[i] = out[i];  } 

the problem order in allocate array of counters: when write

copy = (int*) malloc(sizeof(int) * max); 

the max not set, value undefined. therefore, allocation produces undefined behavior, making program invalid.

you need move allocation past loop computes max. allocate max+1 items, because array indexes zero-based:

int max = array[0]; for(i=0;i<n;++i)     if(array[i] > max)         max = array[i]; copy = malloc(sizeof(int) * (max+1)); 

you need free both copy , out @ end avoid memory leaks:

free(copy); free(out);