Heap Sort

Heap sort It is a combination of Build Heap(n) + heapify(log n) + getting max + heapify(n log n)

class Solution
{
public:
    void max_heapify(vector<int> &v, int n, int pos)
    {

        int largest = pos;

        int lc = pos * 2 + 1;
        int rc = pos * 2 + 2;

        if (lc < n && v[lc] > v[largest])
        {
            largest = lc;
        }

        if (rc < n && v[rc] > v[largest])
        {
            largest = rc;
        }

        if (largest != pos)
        {
            swap(v[pos], v[largest]);
            max_heapify(v, n, largest);
        }

        return;
    }

    void buildHeap(vector<int> &v)
    {
        int n = v.size();
        for (int i = (n / 2) - 1; i >= 0; i--)
        {
            max_heapify(v, n, i);
        }

        return;
    }

    vector<int> sortArray(vector<int> &nums)
    {
        buildHeap(nums);

        int n = nums.size();

        for (int i = n - 1; i >= 1; i--)
        {
            swap(nums[0], nums[i]);
            max_heapify(nums, i, 0);
        }

        return nums;
    }
};

Time Complexity: O(n log n)