Sorting

Merge Sort:
Complexity: O(n*log(n))

void merge(int l, int r, int mid, vector<int> &v) {
    int l_sz = mid - l + 1;
    vector<int> L(l_sz + 1);
    int r_sz = r - mid;
    vector<int> R(r_sz + 1);
    for(int i = 0; i < l_sz; ++i) L[i] = v[i+l];
    for(int i = 0; i < r_sz; ++i) R[i] = v[i+mid+1];
    L[l_sz] = R[r_sz] = INT_MAX;
    int l_i = 0, r_i = 0;
    for(int i = l; i <= r; ++i) {
        if(L[l_i] <= R[r_i]) v[i] = L[l_i++];
        else v[i] = R[r_i++];
    }
}
void msrt(int l, int r, vector<int> &v) {
    if(l == r) return;
    int mid = (l + r) >> 1;
    msrt(l, mid, v);
    msrt(mid + 1, r, v);
    merge(l, r, mid, v);
}

Quick Sort:

Complexity: O(n*log(n))

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) swap(arr[++i], arr[j]);
    }
    swap(arr[i + 1], arr[high]); return (i + 1);
}
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

Heap Sort:
Complexity: O(n*log(n))

void heapify(int ar[], int n, int i) {
    int mx = i, l = (i << 1) + 1, r = (i << 1) + 2;
    if (l < n && ar[l] > ar[mx]) mx = l;
    if (r < n && ar[r] > ar[mx]) mx = r;
    if (mx != i) {
        swap(ar[i], ar[mx]);
        heapify(ar, n, mx);
    }
}
void hsrt(int ar[], int n) {
    for (int i = (n >> 1) - 1; i >= 0; --i)
        heapify(ar, n, i);
    for (int i = n - 1; i > 0; --i) {
        swap(ar[0], ar[i]);
        heapify(ar, i, 0);
    }
}