# Sorting Algorithms

```class Solution
{
public:
void insertionSort(int arr[], int n)
{
int value,hole;
for(int i=0;i<n;i++){
value=arr[i];hole=i;
while(hole>0&&arr[hole-1]>value){
arr[hole]=arr[hole-1];
hole--;
}
arr[hole]=value;
}
}
};```
```class Solution
{
public:
int select(int arr[], int i)
{
int max = arr[0], ind = 0;
int j;
for ( j=1; j<=i; j++)
{
if (arr[j] > max)
{
ind = j;
max = arr[j];
}
}
return ind;
}

void selectionSort(int arr[], int n)
{
int i, j;
for (i = n-1; i >=0; i--)
{
int j = select(arr, i);
swap(&arr[i], &arr[j]);
}
}
};```
```class Solution
{
public:
//Function to sort the array using bubble sort algorithm.
void bubbleSort(int arr[], int n)
{
int flag=0;
for(int k=1;k<=n-1;k++){
for(int j=0;j<=n-k-1;j++){
if(arr[j]>arr[j+1]){
swap(&arr[j],&arr[j+1]);
flag=1;
}
}
if(flag==0)
break;
}
}
void swap(int *xp,int *yp){
int temp=*xp;
*xp=*yp;
*yp=temp;
}
};```
```class Solution
{
public:
void merge(int arr[], int l, int m, int r)
{
int n1=m-l+1;
int n2=r-m;
// Initialization of temp arrays
int L[n1],R[n2];
// Initialization of first subarray
for(int i=0;i<n1;i++)
L[i]=arr[l+i];
// Initialization of second subarray
for(int j=0;j<n2;j++)
R[j]=arr[m+1+j];
int i=0,j=0,k=l;
//Sorting the array using subarrays
while(i<n1&&j<n2){
if(L[i]<R[j]){
arr[k]=L[i];
i++;
}
else {
arr[k]=R[j];
j++;
}
k++;
}
//Remaining elements added to the array
while(i<n1){
arr[k]=L[i];
i++;k++;
}
while(j<n2){
arr[k]=R[j];
j++;k++;
}
}
public:
void mergeSort(int arr[], int l, int r)
{
if(l>=r)
return; //returns recursively
int m=l+(r-l)/2;
mergeSort(arr,l,m);
mergeSort(arr,m+1,r);
merge(arr,l,m,r);
}
};```