# Merge Sort

Merge Sort is a one of the sorting techniques in data structure.

It is a simple technique to sort the element.

Merge  is also used for sorting two individual unsorted list to sorted list.

It merge the list.

## Merge sort technique

In this technique we have a N number of unsorted list in this, We divide each element into a separate partition.

First, We divide the whole list into two array then that two array are divided separately and sort the each element after that we merge the partitioned set to one single array. Finally, We will get our sorted array by merge sort technique.

## Algorithm

1. Take a set of number an array.
2. Divide the array into equal parts.
3. Consider these two parts separately
4. Now, Take first part and partition the number until we have only one element left then start combining the each number by comparing and arrange in order.
5. For second part also, Partition the each number until one number left then start combining each number by comparing and arranging in order.
6. After this, Compare the two sorted array and arrange into a one sorted list.
7. Finish

Example:-

Output :-

Sorted list – 3 9 10 27 38 43 82

In this way we will get the sorted list.

The passes or steps required for implementing merge Sort is N -1.

The time complexity for merge Sort is O(n log n) for worst case.

1. It is very simple and easy sorting technique.
2. Works very good for large data.