Basic Sorting Algorithms

So today , we will be talking about sorting algorithms,

The most basic sorting algorithm is bubble sort.
Let us have an array of length n ;
Then we iterate over the whole array and for every element we check all the following elements :
If any element has a value greater than the given element we swap the elements .
In the end  We will have an array sorted in ascending order.
Here is the code snippet for it :-
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{

If(arr[i]>arr[j])
{
swap(arr[i],arr[j]);
}
}
You could make this more efficient by first finding the minimum value and then swapping , that is called the insertion sort.

Now , this algorithm takes O((n^2) time , and hence is not efficient .

So we go on to look to a sorting algorithm which takes O(nlogn) time complexity.

It is called mergesort

It has a recursion based approach .
So the code works as follows , divide the array into two parts , then call mergesort for both halves and merge the two parts .

This time complexity can be found by the recursion tree.
Here is the code snippet :-

void merge(int A[ ] , int start, int mid, int end) {
 //stores the starting position of both parts in temporary variables.
int p = start ,q = mid+1;

int Arr[end-start+1] , k=0;

for(int i = start ;i <= end ;i++) {
    if(p > mid)      //checks if first part comes to an end or not .
       Arr[ k++ ] = A[ q++] ;

   else if ( q > end)   //checks if second part comes to an end or not
       Arr[ k++ ] = A[ p++ ];

   else if( A[ p ] < A[ q ])     //checks which part has smaller element.
      Arr[ k++ ] = A[ p++ ];

   else
      Arr[ k++ ] = A[ q++];
 }
  for (int p=0 ; p< k ;p ++) {
   /* Now the real array has elements in sorted manner including both 
        parts.*/
     A[ start++ ] = Arr[ p ] ;                          
  }
}

We finally discuss the easiest option we have is to use the C++ stl library inbuilt function of sort.
It is the most efficient sorting algorithm and works in O(nkogn) time.
It is a mixture of quicksort,radixsort and mergesort.

It can be used as follows by including the <algorithm> library

std::sort(arr,arr+n)

It has the parameters , 1. Starting pointer ,
                                    2. Ending pointer ,
                                    3. Function on the basis of which to sort (ascending is by default :- this parameter is optional)

Please leave any comments for any doubts