In computer science, a merge sort (also commonly spelled mergesort) is an O(n log n) comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Mergesort is a divide and conquer algorithm that was invented by John von Neumann in 1945. A detailed description and analysis of bottom-up mergesort appeared in a report by Goldstine and Neumann as early as 1948.
The Divide and Conquer paradigm involves three steps at each level of the recursion.
- Divide the problem into a number of subproblems. Divide the n-element sequence to be sorted into two subsequences of n/2 elements each.
- Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, just solve the subproblems in a straightforward manner. Sort the two subsequences using merge sort.
- Combine the solutions to the subproblems into the solution for the original problem. Merge the two sorted subsequences to produce sorted answer.
Algorithm for Merge Sort:
Here A is an array p is start, q mid and r is the last item index. So A[p...r] is the full array that breaks up into A[p...q] and A[q+1...r]. So here is the Algorithm. The Algorithm is divided into two steps one is MERGE procedure that takes up two subsequences and merge them or combine them as per the values and MERGE-SORT that break up a Sequence into two subsequences.
n1 = q-p+1
n2 = r-q
create_arrays L[1...n1+1] and R[1...n2+1]
for i=1 to n1
do L[i] = A[p+i-1]
for j=1 to n2
do R[j] = A[q+j]
L[n1+1] = infinite
R[n2+1] = infinite
i = 1
j = 1
for k=p to r
do if L[i] <= R[j]
then A[k] = L[i]
else A[k] = R[j]
if p < r
then q = [(p+r)/2]
Merge Sort Implementation of the above algorithm taken from Introduction to Algorithms by CLRS.
One more optional Implementation also.