Following is a typical recursive implementation of Merge Sort that uses last element as pivot. Python]
Python Program for Iterative Merge Sort
The provided Python code demonstrates the recursive implementation of the Merge Sort algorithm. Merge Sort divides an array into smaller subarrays, sorts them, and then merges them back together to achieve a sorted result. The code comprises two main functions: merge to combine two sorted arrays, and mergesort to recursively split and sort an array. The merge function compares elements from the left and right arrays, creating a sorted result array. The mergesort function repeatedly divides the array until its subarrays have one element, then merges them back. The example sorts an array using Merge Sort and prints both the original and sorted arrays, highlighting the recursive nature of the algorithm.
Python
# Recursive Python Program for merge sortdef merge(left, right): if not len(left) or not len(right): return left or right result = [] i, j = 0, 0 while (len(result) < len(left) + len(right)): if left[i] < right[j]: result.append(left[i]) i+= 1 else: result.append(right[j]) j+= 1 if i == len(left) or j == len(right): result.extend(left[i:] or right[j:]) break return resultdef mergesort(list): if len(list) < 2: return list middle = len(list)/2 left = mergesort(list[:middle]) right = mergesort(list[middle:]) return merge(left, right) seq = [12, 11, 13, 5, 6, 7]print("Given array is")print(seq);print("\n")print("Sorted array is")print(mergesort(seq))# Code Contributed by Mohit Gupta_OMG |
Given array is [12, 11, 13, 5, 6, 7] Sorted array is [5, 6, 7, 11, 12, 13]
Time Complexity: O(n*log(n))
Auxiliary Space: O(n)
Please refer complete article on Iterative Merge Sort for more details!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
