Step 1:
void interchange(int *a, int *b) {
...
temp = *a; *a = *b; *b = temp;
}
void quicksort(int *arr, int m, int n) {
...
if (m < n) {
i = m; j = n+1; k = arr[m];
do {
do { i = i + 1; } while (arr[i] > k);
do { j = j - 1; } while (arr[j] < k);
if (i < j) interchange(&arr[i], &arr[j]);
} while (i < j);
interchange(&arr[m], &arr[j]);
quicksort(arr, m, j - 1);
quicksort(arr, j + 1, n);
}
}
void sort_5elements(int *arr) {
quicksort(arr, 0, 4);
}
int select_kth_largest(int k, int *S, int n) {
...
n_M = ceil(n, 5);
for (i=0; i< n_M; i++) {
sort_5elements(&S[5*i]);
}
S1 = (int *) malloc ((3*n/4) * sizeof(int));
S3 = (int *) malloc ((3*n/4) * sizeof(int));
for (i=0; i< n_M; i++)
M[i] = S[middle(i)];
m = select_kth_largest(ceil(n_M,2), M, n_M);
...
}