```
int main()
{
int n=6;
int a[n] = {6,5,4,3,2,1};
int temp;
for(int i = 0; i < n; i++)
{
for( int j = i+1; j < n; j++ )
{
if( a[i] > a[j] )
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
for( int i = 0; i < n; i++ )
{
cout << a[i] << " ";
}
return 0;
}
```

To sort an array of size n in ascending order:

1: Iterate from arr[1] to arr[n] over the array.

2: Compare the current element (key) to its predecessor.

3: If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

```
int main()
{
int n=6;
int a[n] = {6,2,4,3,5,1};
int key, j;
for( int i = 0; i < n; i++ )
{
key = a[i];
j = i-1;
while( j >= 0 && a[j] > key )
{
a[j+1] = a[j];
j--;
}
a[j+1] = key;
}
for( int i = 0; i < n; i++ )
{
cout << a[i] << " ";
}
return 0;
}
```

1) The subarray which is already sorted.

2) Remaining subarray which is unsorted.

In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.

```
int main()
{
int n=6;
int a[n] = {6,2,4,3,5,1};
int sIndex;
int temp;
for( int i = 0; i < n; i++ )
{
sIndex = i;
for( int j = i; j < n; j++ )
{
if( a[sIndex] > a[j] )
{
sIndex = j;
}
}
temp = a[i];
a[i] = a[sIndex];
a[sIndex] = temp;
}
for( int i = 0; i < n; i++ )
{
cout << a[i] << " ";
}
return 0;
}
```

The good thing about selection sort is it never makes more than O(n) swaps and can be useful when memory write is a costly operation.

```
void mergeArr(int a[], int l, int m, int r)
{
int n1 = m-l+1;
int n2 = r-m;
int L[n1], R[n2];
for(int i = 0; i < n1; i++)
{
L[i] = a[l+i];
}
for( int i = 0; i < n2; i++ )
{
R[i] = a[m+1+i];
}
int i=0, j=0;
int k=l;
while( i < n1 && j < n2 )
{
if( L[i] <= R[j] )
{
a[k] = L[i];
i++;
} else
{
a[k] = R[j];
j++;
}
k++;
}
while( i < n1 )
{
a[k] = L[i];
i++;
k++;
}
while( j < n2 )
{
a[k] = R[j];
j++;
k++;
}
}
void mergeSort(int a[], int l, int r)
{
if( l >= r )
{
return;
}
int m = (r-l)/2 + l;
mergeSort(a, l, m);
mergeSort(a, m+1, r);
mergeArr(a, l, m, r);
}
void printArr(int a[], int n)
{
for( int i = 0; i < n; i++ )
{
cout << a[i] << " ";
}
cout << endl;
}
int main()
{
int n = 7;
int a[n] = {6,7,5,4,3,2,1};
mergeSort(a, 0, n-1);
printArr(a, n);
return 0;
}
```

- Slower comparative to the other sort algorithms for smaller tasks.
- Merge sort algorithm requires an additional memory space of 0(n) for the temporary array
- It goes through the whole process even if the array is sorted

- Always pick first element as pivot
- Always pick last element as pivot (implemented below)
- Pick a random element as pivot
- Pick median as pivot

```
void elementSwap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
int makePartition(int a[], int s, int e)
{
int pevot = a[e];
int pIndex = s;
for( int i = s; i < e; i++ )
{
if( a[i] <= pevot )
{
elementSwap(&a[i], &a[pIndex]);
pIndex++;
}
}
elementSwap(&a[e], &a[pIndex]);
return pIndex;
}
void quickSort(int a[], int s, int e)
{
if( s >= e )
{
return;
}
int p = makePartition(a, s, e);
quickSort(a, s, p-1);
quickSort(a, p+1, e);
}
void printArr(int a[], int n)
{
for( int i = 0; i < n; i++ )
{
cout << a[i] << " ";
}
cout << endl;
}
int main()
{
int n = 6;
int a[n] = {6,5,4,3,2,1};
quickSort(a, 0, n-1);
printArr(a, n);
return 0;
}
```

- Best case: ?(nLogn)
- Average case: O(nLogn)
- Worst caseL O(n^2)

Quick Sort in its general form is an in-place sort (i.e. it does not require any extra storage) whereas merge sort requires O(N) extra storage, N denoting the array size which may be quite expensive. Allocating and de-allocating the extra space used for merge sort increases the running time of the algorithm. Comparing average complexity we find that both type of sorts have O(NlogN) average complexity but the constants differ. For arrays, merge sort loses due to the use of extra O(N) storage space.

Most practical implementations of Quick Sort use randomized version. The randomized version has expected time complexity of O(nLogn). The worst case is possible in randomized version also, but worst case does not occur for a particular pattern (like sorted array) and randomized Quick Sort works well in practice.

Quick Sort is also a cache friendly sorting algorithm as it has good locality of reference when used for arrays.

Quick Sort is also tail recursive, therefore tail call optimizations is done.