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:

1. Divide: Divide the array into two halves.
2. Recursively Sort: Recursively sort each half of the array.
3. 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.