Merge Sort belongs to category of divide and conquer algorithms. Which means it divides the problem into small subproblems, solves them and then combine the solutions of these subproblems to generate solution of the original problem.Merge Sort compares elements with each other for sorting the list.
The steps followed to mergesort are are:
- Divide the unsorted list into n sublists, each containing single element .
- Repeatedly merge(involves comparing elements of the sublists) sublists to produce new sublists until there is only 1 sublist remaining. This will be the sorted list.
For more information on merge sort visit http://en.wikipedia.org/wiki/Merge_sort
Below is the code for merge sort algorithm.
*Program to sort numbers using <strong>MERGESORT</strong>
*inputs: N- number of integers to sort ,A-array of integers
*output: sorted array of integers
void mergesort(int A,int p,int r,int O)
if( p < r)
void merge(int A,int p,int q,int r,int O)
//Note that I have intionally used few extra lines in all of the follwing loops tomake it more clear to learners