Как оптимизировать код для сортировки массива в C++?

---

Я написал программу для сортировки массива для задачи Hackerrank median, мой код проходит 3/4 тестовых заданий. Последний тестовый случай завершается неудачей из-за таймаута, когда общее количество элементов массива равно 10001. Как я могу оптимизировать этот код, чтобы предотвратить тайм-ауты с более высокими числами?

#include<iostream>
using namespace std;
int main() {
    int n,j,i,tmp,med;
    cin >> n;
    int *a = (int*) malloc(n * sizeof(int));
    for(i=0; i<n; i++) 
        cin >> a[i];
    for(i=0; i<n-1; i++) {
        for(j=0; j<n-i-1; j++) {
            if(a[j] > a[j+1]) {
                tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;
            }
        }
    }
    med = a[n/2];
    free(a);
    cout << med;
    return 0;
}

Что я уже пробовал:

Я попытался изменить целое число на long int, но временная сложность осталась прежней.

---