Merge Sort Algorithm with example

SORTING

Sorting is the process of arranging given numbers or elements in ascending or descending order.

Other sorting techniques

• Insertion sort
• Quick sort
• Heap sort
• Bucket sort
• Shell sort
• Radix sort etc.

MERGE SORT

Merge sort is a recursive algorithm based on Divide and Conquer technique. Note that Bubble and Selection sorts are ITERATIVE algorithms. Merge sort based on Divide, Conquer and Merge (combine) techniques. First the list to be sorted is divided into TWO HALFS. Each HALF is sorted independently (CONQUER). The two sorted halfs merged to a sorted list (COMBINE). It operates as follows:

MERGE SORT ALGORITHM IS AS FOLLOWS:

1. If the length of the list is 0 or 1, then it is already sorted.
2. Divide the unsorted list into two sub-lists, if possible equal size.
3. The sub-lists are again divided repeatedly until single element.
4. Sort each sub-list recursively.
5. Merge the sub-lists back into one sorted list.

DESCRIPTION OF MERGING TWO SORTED LISTS IS AS FOLLOWS

1. Create two pointers (indexes) pointing to the beginning of the two given lists – B & C.
2. Compare the elements they points to. Pick the smaller element among B & C and put it into the answer list A i.e. the merged list under construction and increment the corresponding pointer.
3. Repeat the above step 2 until one of the two lists is empty. Then copy the remaining elements from the other list or array into the merged array.