14.
Explanation
Merge sort is a popular and efficient comparison-based sorting algorithm that follows the divide-and-conquer strategy. It divides the unsorted array into two halves, recursively sorts these halves, and then merges them back together. Here's the algorithm for merge sort:
Algorithm for Merge Sort:
1. Divide the unsorted array into two halves, a left subarray, and a right subarray.
◦ Calculate the middle of the array: mid = (left + right) / 2.
2. Recursively sort the left subarray:
◦ Call MergeSort(arr, left, mid).
3. Recursively sort the right subarray:
◦ Call MergeSort(arr, mid + 1, right).
4. Merge the two sorted subarrays back together:
◦ Create an auxiliary array to hold the merged result.
◦ Initialize three indices: i for the left subarray, j for the right subarray, and k for the merged array.
◦ Compare elements at indices i and j from the left and right subarrays, respectively.
◦ Place the smaller of the two elements in the merged array and increment the respective index.
◦ Repeat this process until both subarrays are fully merged.
5. The array is now sorted.
The merge sort algorithm in Python:
def mergeSort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
mergeSort(left_half)
mergeSort(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:
arr = [64, 34, 25, 12, 22, 11, 90]
mergeSort(arr)
print("Sorted array:", arr)
Merge sort guarantees a time complexity of O(n log n), making it an efficient sorting algorithm, particularly for large datasets. It is a stable sort and works well for both arrays and linked lists.