# Merge Sort Algorithm

## Introduction to Merge Sort

Merge sort is a divide-and-conquer sorting algorithm that divides the input array into two halves, recursively sorts each half, and then merges the sorted halves to produce the sorted array. It has a time complexity of O(n log n) and is efficient for large data sets.

## Step-by-Step Process

Consider an array with the following elements:

```
[38, 27, 43, 3, 9, 82, 10]
```

To sort this array using merge sort, follow these steps:

**Divide**: Divide the array into two halves.**Recursively Sort**: Recursively sort each half of the array.**Merge**: Merge the two sorted halves to produce the final sorted array.

Let's apply these steps to the example array:

- Initial array: [38, 27, 43, 3, 9, 82, 10]
- Divide: [38, 27, 43] and [3, 9, 82, 10]
- Recursively sort first half: [27, 38, 43]
- Recursively sort second half: [3, 9, 10, 82]
- Merge: [3, 9, 10, 27, 38, 43, 82]

## Pseudo Code for Merge Sort

Below is the pseudo code for the merge sort algorithm:

```
function mergeSort(array)
if length(array) > 1 then
mid = length(array) / 2
leftHalf = array[0...mid]
rightHalf = array[mid...length(array)]
mergeSort(leftHalf)
mergeSort(rightHalf)
i = 0
j = 0
k = 0
while i < length(leftHalf) and j < length(rightHalf) do
if leftHalf[i] < rightHalf[j] then
array[k] = leftHalf[i]
i = i + 1
else
array[k] = rightHalf[j]
j = j + 1
end if
k = k + 1
end while
while i < length(leftHalf) do
array[k] = leftHalf[i]
i = i + 1
k = k + 1
end while
while j < length(rightHalf) do
array[k] = rightHalf[j]
j = j + 1
k = k + 1
end while
end if
end function
```

Explanation:

**Divide**: The mergeSort function starts by dividing the array into two halves if the length of the array is greater than one.**Recursively Sort**: Each half is recursively sorted by calling the mergeSort function on the left and right halves.**Merge**: The merge step combines the two sorted halves by comparing the elements and arranging them in order. This is done using three pointers to track the current index of the left half, right half, and the main array.**Combine**: The remaining elements of the left half and right half, if any, are copied to the main array.

## Python Program to Implement Merge Sort

```
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
merge_sort(left_half)
merge_sort(right_half)
i = j = k = 0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
# Example usage:
array = [38, 27, 43, 3, 9, 82, 10]
print("Original array:", array)
merge_sort(array)
print("Sorted array:", array) # Output: [3, 9, 10, 27, 38, 43, 82]
```

This Python program defines a function to perform merge sort on an array. The function divides the array into two halves, recursively sorts each half, and then merges the sorted halves to produce the final sorted array.