Merge Sort in Python
Merge Sort is an efficient sorting algorithm that uses the merge operation. It is a classic example of the Divide and Conquer strategy, which breaks the problem into smaller subproblems, solves them recursively, and then combines the solutions.
Divide and Conquer Strategy:
Divide: Recursively divide the current sequence into two halves.
Conquer (Merge): Combine the two halves while keeping the elements in order (merge step).
Example
Here is the implementation of Merge Sort in Python:
def merge(arr, l, m, r):
n1 = m - l + 1
n2 = r - m
# Create temporary arrays
L = [0] * (n1)
R = [0] * (n2)
# Copy data to temporary arrays L[] and R[]
for i in range(0, n1):
L[i] = arr[l + i]
for j in range(0, n2):
R[j] = arr[m + 1 + j]
# Merge the temporary arrays back into arr[l..r]
i = 0 # Initial index of the first subarray
j = 0 # Initial index of the second subarray
k = l # Initial index of the merged subarray
while i < n1 and j < n2:
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
# Copy the remaining elements of L[], if any
while i < n1:
arr[k] = L[i]
i += 1
k += 1
# Copy the remaining elements of R[], if any
while j < n2:
arr[k] = R[j]
j += 1
k += 1
# Main function that implements Merge Sort
def mergeSort(arr, l, r):
if l < r:
# Find the middle point
m = int((l + (r - 1)) / 2)
# Sort first and second halves
mergeSort(arr, l, m)
mergeSort(arr, m + 1, r)
# Merge the sorted halves
merge(arr, l, m, r)
# Example array
arr = [12, 11, 13, 5, 6, 7]
n = len(arr)
print("Given array:")
for i in range(n):
print("%d" % arr[i], end=" ")
mergeSort(arr, 0, n - 1)
print("\n\nSorted array:")
for i in range(n):
print("%d" % arr[i], end=" ")Output:
Given array: 12 11 13 5 6 7 Sorted array: 5 6 7 11 12 13
In this example, the array [12, 11, 13, 5, 6, 7] is sorted using the Merge Sort algorithm. After dividing the array into smaller parts and merging them back in order, the final sorted array is [5, 6, 7, 11, 12, 13].
