me 6 MEDIAN NI TIM

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void swap(int *a, int *b)
{
   int t;
   t  = *b;
   *b = *a;
   *a = t;
}

void insertion_sort(int A[], int from, int to) {
    for(int i = from; i < to; i++) {
        for(int j = i + 1; j > from && A[j] < A[j - 1]; j--) {
            int temp = A[j - 1];
            A[j - 1] = A[j];
            A[j] = temp;
        }
    }
}

int find_median(int A[],int p,int r)
{
    int n = r-p+1;
    insertion_sort(A,p,r);
    return A[n+1/2];
}

int quick_select(int A[], int p, int r, int k);

int median_of_medians(int A[], int p, int r){
    int N = r-p+1; // N of ORIGINAL array
    int Copy[N+1]; // plus 1 cuz 1-indexed lol
    for (int i=0; i<N; i++){
        Copy[i] = A[i];
    }

    int groups_no = ceil(N/5); // N of NEW subarray which will contain the median(s)
    int Medians[groups_no+1]; // array which contains the median(s)
    for (int i=p; i < groups_no+1; i++){
        if (i < groups_no){ // FIRST NEW-1 GROUPS (guaranteed N 5 each)
            insertion_sort(Copy, i*5-4, i*5); // minus cuz 1-indexed
            Medians[i] = Copy[i*5-2]; // say i=2. then the median of the 2nd group is at index 8.
        } else if (i == groups_no){ // LAST GROUP
            int rem = N % 5;
            if (rem == 0){
                insertion_sort(Copy, i*5-4, i*5);
                Medians[i] = Copy[i*5-2];
            } else {
                insertion_sort(Copy, i*5-4, i*5-(5-rem));
                int med = (rem+1)/2;
                Medians[i] = Copy[i*5+med];
            }
        }
    }
    if (groups_no > 5){
        return quick_select(Medians, 1, groups_no, (groups_no+1)/2);
    } else {
        int med = (groups_no+1)/2;
        return Medians[med];
    }

}

int partition(int A[], int p, int r){
    int M = (r-p)+1;
    int median = median_of_medians(A,p,r);
    int ind;
    for(int i = p;i<=r;i++)
    {
        if(A[i]== median)
        {
            ind = i;
        }
    }
    swap(&A[ind],&A[r]);
    int x = A[r];
    int i = p-1;
    for(int j = p;j<=(r-1);j++)
    {
        if(A[j] <= x)
        {
            i++;
            swap(&A[i],&A[j]);
        }
    }
    swap(&A[i+1],&A[r]);
    return i+1;
}

int quick_select(int A[], int p, int r, int rank){
    if(p == r)
    {
        return A[p];
    }
    int q = partition(A,p,r);
    int k = q-p+1;
    if(rank == k)
    {
        return A[q];
    }
    else if (rank < k)
    {
        return quick_select(A,p,q-1,rank);
    }
    else
    {
        return quick_select(A,q+1,r,rank-k);
    }
}

int main(){
    int T, M;
    scanf("%d", &T);
    while(T-- > 0){
        scanf("%d", &M);
        int arr[M+1];

        //read the elements of the input array
        for(int i=1; i<=M; i++){
            scanf("%d",&arr[i]);
        }

        int median_index = ((M+1)/2);
        printf("Median: %d\n", quick_select(arr, 1, M, median_index));
    }
}