### Sorting

#### Description:

Alice uses the following pseudocode when she needs to sort a permutation of Npositive integers: procedure Sort(list A) defined as: list less, greater if length(A) <= 1 then return A pivot := A(length(A)+1) / 2 for i := 1 to length(A) do: Increment(comparison_count) if Ai < pivot then append Ai to less else if Ai > pivot append Ai to greater end if end for return concatenate(Sort(less), pivot, Sort(greater) ) And now we are interested in the number of comparisons that will be made during the sorting of the given permutation of integers A with the provided code. So, we ask you to find the value of the variable comparison_count after such a sorting. Input The first line of input consists of a single integer N. The second line of input contains a permutation of N numbers. Output Output the number of comparisons on the first and only line of the output. Example Input: 5 4 3 5 1 2 Output: 11

#### Program :

```#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <time.h>
#include <limits.h>

int comparison_count;

void debug_array(int *array, int array_size) {
printf("\n");
printf("[");
int i;
for (i = 0; i < array_size; i++) {
printf("%3d", array[i]);
}
printf("]");
printf("\n");
}

unsigned long long bigrand() {
unsigned long long big_rand = 0;
big_rand = rand();
big_rand = big_rand << 32;
big_rand |= rand();
return big_rand;
}

int randint(int start_range, int end_range) {
return  (bigrand() % ((end_range + 1) - start_range)) + start_range;
}

void concatenate(int *concatenated,
int concatenated_size,
int *less,
int less_size,
int pivot,
int *greater,
int greater_size) {
int concatenated_idx = 0;
int i;
for (i = 0; i < less_size; i++) {
concatenated[concatenated_idx++] = less[i];
}
concatenated[concatenated_idx++] = pivot;
for (i = 0; i < greater_size; i++) {
concatenated[concatenated_idx++] = greater[i];
}
}

int *sort(int *array, int array_size) {
if (array_size <= 1) {
return array;
}
int pivot = array[(array_size - 1) / 2];
int *less = calloc(array_size, sizeof(int));
int less_idx = 0;
int *greater = calloc(array_size, sizeof(int));
int greater_idx = 0;
memset(less, -1, array_size * sizeof(int));
memset(greater, -1, array_size * sizeof(int));
int i;
for (i = 0; i < array_size; i++) {
comparison_count++;
if(array[i] < pivot) {
less[less_idx++] = array[i];
} else if (array[i] > pivot) {
greater[greater_idx++] = array[i];
}
}

int concatenated_size = less_idx + greater_idx + 1;
int *concatenated = calloc(concatenated_size, sizeof(int));
concatenate(concatenated,
concatenated_size,
sort(less, less_idx),
less_idx,
pivot,
sort(greater, greater_idx),
greater_idx);
return concatenated;
}

float calc_elapsed_time(clock_t time_s, clock_t time_e) {
return (((float)time_e - (float)time_s) / CLOCKS_PER_SEC) * 1000;
}

int main(int argc, const char * argv[])
{

int N;
scanf("%d", &N);
int *A = calloc(N, sizeof(int));
int i;
for (i = 0; i < N; i++) {
scanf("%d", &A[i]);
}
comparison_count = 0;

int *sorted = sort(A, N);
free(sorted);

printf("%d\n", comparison_count);
return 0;
}
```