# Merge Sort Algorithm in data structure

Merge Sort is a sorting algorithm, which is commonly used in computer science for break things up along useful lines. If we're sorting change, we first divide the coins up by denominations, then total up each denomination before adding them together.

Merge Sort is a Divide and Conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.

The merge() function is used for merging two halves. The merge(arr, l, m, r) is a key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one.

MergeSort(arr[], l,  r)

If r > l

1. Find the middle point to divide the array into two halves: middle m = l+ (r-l)/2

2. Call mergeSort for first half: Call mergeSort(arr, l, m)

3. Call mergeSort for second half: Call mergeSort(arr, m+1, r)

4. Merge the two halves sorted in step 2 and 3: Call merge(arr, l, m, r)

For example:

The following example shows the complete merge sort process

for an example array {38, 27, 43, 3, 9, 82, 10}. If we take a closer look at the diagram, we can see that the array is recursively divided into two halves till the size becomes 1. Once the size becomes 1, the merge processes come into action and start merging arrays back till the complete array is merged.