Merge Sort Method
Simple merge sort is used to merge two sorted list in a single sorted list.
In a simple merge sort we compare the elements of both lists and the element which has the smallest value is placed in a new list.
This process is repeated until all the elements from both the lists are placed in a new list.
Consider the following example:
List1: 28 31 37 39
List2: 24 35 43 53 85 89
First we compare the elements of both the lists and the element which has the smallest value is placed in a new table.
Trace of Simple Merge Sort
| Comparisions |
Content of New List |
|
Empty |
| Compare 28 with 24. 24 is smaller so it is placed in New List. |
24 |
| Compare 28 with 35. 28 is smaller so it is placed in New List. |
24 28 |
| Compare 31 with 35. 31 is smaller so it is placed in New List. |
24 28 31 |
| Compare 37 with 35. 35 is smaller so it is placed in New List. |
24 28 31 35 |
| Compare 37 with 43. 37 is smaller so it is placed in New List. |
24 28 31 35 37 |
| Compare 39 with 43. 39 is smaller so it is placed in New List. |
24 28 31 35 37 39 |
| Now List1 is empty so place remaining elements of List2 in New List. |
24 28 31 35 37 39 43 53 85 89 |
