MergeSort
MergeSort is an efficient, divide-and-conquer sorting algorithm that divides the input array into two halves, recursively sorts the two halves, and then merges them to produce a sorted output.
The steps involved in the MergeSort algorithm are as follows:
- Divide the input array into two halves by finding the middle index.
- Recursively sort the left and right halves using MergeSort.
- Merge the two sorted halves into a single sorted array.
The merging step is the most critical part of the MergeSort algorithm. It involves comparing elements from both halves and selecting the smaller (or larger) element at each step to form the final sorted array.
Here's a Python implementation of the MergeSort algorithm:
1# Merge two subarrays of arr[]
2# First subarray is arr[l..m]
3# Second subarray is arr[m+1..r]
4
5def merge(arr, l, m, r):
6 n1 = m - l + 1
7 n2 = r - m
8
9 # Create temporary arrays
10 L = [0] * n1
11 R = [0] * n2
12
13 # Copy data to temporary arrays
14 for i in range(n1):
15 L[i] = arr[l + i]
16
17 for j in range(n2):
18 R[j] = arr[m + 1 + j]
19
20 # Merge the temporary arrays
21 i = 0
22 j = 0
23 k = l
24
25 while i < n1 and j < n2:
26 if L[i] <= R[j]:
27 arr[k] = L[i]
28 i += 1
29 else:
30 arr[k] = R[j]
31 j += 1
32 k += 1
33
34 # Copy the remaining elements of L[]
35 while i < n1:
36 arr[k] = L[i]
37 i += 1
38 k += 1
39
40 # Copy the remaining elements of R[]
41 while j < n2:
42 arr[k] = R[j]
43 j += 1
44 k += 1
45
46
47# Main function to perform MergeSort
48
49def mergeSort(arr, l, r):
50 if l < r:
51 # Find the middle point
52 m = (l + (r - 1)) // 2
53
54 # Sort first and second halves
55 mergeSort(arr, l, m)
56 mergeSort(arr, m + 1, r)
57
58 # Merge the sorted halves
59 merge(arr, l, m, r)
60
61
62if __name__ == '__main__':
63 arr = [64, 34, 25, 12, 22, 11, 90]
64 n = len(arr)
65
66 print('Original array:', arr)
67
68 mergeSort(arr, 0, n - 1)
69
70 print('Sorted array:', arr)In this example, we define a function mergeSort that takes an input array and the indices of the first and last elements to be sorted. The function recursively divides the array into smaller subarrays and calls itself until the base case is reached (when the subarray size is 1). Finally, the function merge is called to merge the sorted subarrays together.
Feel free to modify the code and experiment with different input arrays to see how MergeSort works.
xxxxxxxxxx print('Sorted array:', arr)# Merge two subarrays of arr[]# First subarray is arr[l..m]# Second subarray is arr[m+1..r]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 for i in range(n1): L[i] = arr[l + i] for j in range(n2): R[j] = arr[m + 1 + j] # Merge the temporary arrays i = 0 j = 0 k = l while i < n1 and j < n2: if L[i] <= R[j]: arr[k] = L[i] i += 1 else: