Sorting

Merge Sort (Count Inversions)

Complexity : Worst Case O(n log n)

Quick Sort

Complexity : Worst Case O(n²)

int partition(int l,int r,vector<int>&v)
{
int pivot=(l+r)/2;
while(l<=r)
{
    while(v[l]<v[pivot])
    l++;
    while(v[r]>v[pivot])
     r--;
    if(l<=r)
    {
       swap(v[l],v[r]);
       l++;
        r--;
     }
}
return l;
}
void quicksort(int l,int r,vector<int>&v)
{
   int idx=partition(l,r,v);
   if(l<idx-1)
     quicksort(l,idx-1,v);
   if(idx<r)
     quicksort(idx,r,v);
}
void quick()
{
   vector<int>v;
   v.push_back(10);
   v.push_back(20);
   v.push_back(9);
   v.push_back(3);
   v.push_back(4);
   quicksort(0,v.size()-1,v);
   for(int i=0;i<v.size();i++)
    cout<<v[i]<<" ";
   cout<<endl;
}

Points to remember:

• How do you make the partition algorithm more efficient
• Applications ? (kth largest element, getting k top elements etc. )