## Merge Sort

Merge Sort Algorithm:

• Is based on the divide and conquer approach.
• Divides the list into two sublists of sizes as nearly equal as possible.
• Sorts the two sublists seperately by using merge sort.
• Merges the sorted sublists into one single list.

Algorithm:

MergeSort(low,high)

1. if(low >= high)
• return
2. Set mid = (low+high)/2
3. Divide the list into two sublists of nearly equal lengths and sort each sublist by using merge sort. The steps to do this are as follows:
1. MergeSort(low,mid)
2. MergeSort(mid+1,high)
4. Merge the two sorted sublists:
1. set i = low
2. set j = mid + 1
3. set k = low
4. Repeat until i > mid or j > high //This loop will terminates when you reach the end of one of the two //sublists.
1. if(arr[i] <= arr[j])
1. Store arr[i] at index k in array B
2. Increment i by 1
2. else
1. store arr[j] at index k in array B
2. Increment j by 1
3. Increment k by 1
5. Repeat until j > high //If there are still some elements in the second sublist append them to the new list
1. Store arr[j] at index k in array B
2. Increment j by 1
3. Increment k by 1
6. Repeat until i > mid  //If there are still some elements in the first sublist append them to the new list
1. Store arr[i] at index k in array B
2. Increment i by 1
3. Increment k by 1
5. Copy all elements from the sorted array B in to the original array arr

### Implementing Merge Sort

#include<stdio.h>
#include<conio.h>
#define max 20
void mergesort(int a[],int low, int high);//Divides the array into halves
void merge(int a[],int low,int mid, int high);//Sort and merges subarray
int main()
{
int a[max],i=0,n=0;
printf(“Enter no. of elements\n”);
scanf(“%d”,&n);
printf(“Enter no.\n”);
for(i=0;i<n;i++)
scanf(“%d”,&a[i]);
printf(“Unsorted Array:\t”);
for(i=0;i<n;i++)
printf(“%d\t”,a[i]);
mergesort(a,0,n-1);
printf(“\nSorted Array:\t”);
for(i=0;i<n;i++)
printf(“%d\t”,a[i]);
return 0;
}
void mergesort(int a[],int low,int high)
{
if(low<high)
{
int mid = (low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(a,low,mid,high);
}
}
void merge(int a[],int low, int mid, int high)
{
int high1 = mid-low+1;
int high2 = high-mid;
int i=0,j=0,k=0;
int temp1[high1],temp2[high2]; //Temproary arrys
for(i=0;i<high1;i++) //copy array values in temp arrays
temp1[i] = a[low+i];
for(j=0;j<high2;j++)
temp2[j] = a[mid+1+j];
i=0;
j=0;
k=low;
while(i<high1 && j<high2) //compare elements of subarray
{
if(temp1[i]<temp2[j])
{
a[k] = temp1[i];
i++;
}
else
{
a[k] = temp2[j];
j++;
}
k++;
}
while(i<high1) //copy remaining elements as it is
{
a[k] = temp1[i];
i++;
k++;
}
while(j<high2)
{
a[k] = temp2[j];
j++;
k++;
}
}

If you found any mistakes in above code then please let us know in the comment box below.

Learn Quick Sort Algorithm From Here

## Quick Sort

Quick Sort algorithm:

• is one of the most efficient sorting algorithms.
• is based on divide and conquer approach.
• Successively divides the problem into smaller parts until the problem become so small that they can be directly solved.

In quick sort algorithm, you:

• Select an element from the list called as pivot.
• Partition the list into 2 parts such that:
• All the elements towards the left end of the list are smaller than the pivot.
• All the elements towards the right end of the list are greater than the pivot.
• Store the pivot at its correct position between the two parts of the list.

You repeat this process for each of the two sublists created after partitioning. This process continues untill one element is left in each sublist.

Algorithm:

QuickSort(low,high)

1. if(low>high)
• Return
2. Set pivot = arr[low]
3. set i = low + 1
4. set j = high
5. Repeat step 6 until i < high and arr[i] < pivot //Search for element greater than pivot
6. increment i by 1
7. Repeat step 8 until j > low and arr[j] > pivot //Search for element smaller than pivot
8. Decrement j by 1
9. if i < j     //If greater element is on the left of smaller element
• swap arr[i] with arr[j]
10. if i<=j
• Go to step 5 //Continue the search
11. if low < j
• Swap arr[low] with arr[j] //Swap pivot with last element in first part of the list
12. QuickSort(low,j-1) //Apply quicksort on list left of pivot
13. QuickSort(j+1,high) //Apply quicksort on list right of pivot

### Implementing Quick Sort

#include<stdio.h>
void quicksort(int a[],int low,int high);
int main()
{
int high=0,i=0,arr[20];
printf(“Enter no. of elements\n”);
scanf(“%d”,&high);
printf(“Enter %d numbers to be sorted\n”,high);
for(i=0;i<high;i++)
scanf(“%d”,&arr[i]);
quicksort(arr,0,high-1);
printf(“Sorted Array:\t”);
for(i=0;i<high;i++)
printf(“%d\t”,arr[i]);
return 0;
}
void quicksort(int a[],int low,int high)
{
int first,last,temp,pivot;
pivot = a[low];
first = low+1;
last = high;
if(low<high)
{
while(first<last)
{
while(a[first]<pivot && first < high)
first++;
while(a[last]>pivot && last > low)
last–;
if(first<last)
{
temp = a[first];
a[first] = a[last];
a[last] = temp;
}
}
if(low<last)
{
temp = a[low];
a[low] = a[last];
a[last] = temp;
}
quicksort(a,low,last-1);
quicksort(a,last+1,high);
}
}

If you found any mistakes in above code then please let us know in the comment box below.