In computer science, merge sort is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same in the input and output.
MergeSort(arr, l, r) If r > l Find the middle point to divide the array into two halves: middle m = l+ (r-l)/2 Call mergeSort for first half: Call mergeSort(arr, l, m) Call mergeSort for second half: Call mergeSort(arr, m+1, r) Merge the two halves sorted in step 2 and 3: Call merge(arr, l, m, r)
def mergeSort(arr): if len(arr) >1: mid = len(arr)//2 # Finding the mid of the array L = arr[:mid] # Dividing the array elements R = arr[mid:] # into 2 halves mergeSort(L) # Sorting the first half mergeSort(R) # Sorting the second half i = j = k = 0 # Copy data to temp arrays L and R while i < len(L) and j < len(R): if L[i] < R[j]: arr[k] = L[i] i+= 1 else: arr[k] = R[j] j+= 1 k+= 1 # Checking if any element was left while i < len(L): arr[k] = L[i] i+= 1 k+= 1 while j < len(R): arr[k] = R[j] j+= 1 k+= 1 # Code to print the list def printList(arr): for i in range(len(arr)): print(arr[i], end =" ") print() # driver code to test the above code if __name__ == '__main__': arr = [12, 11, 13, 5, 6, 7] print ("Given array is", end ="\n") printList(arr) mergeSort(arr) print("Sorted array is: ", end ="\n") printList(arr)
All programs will print sorted array as output.
I hope you like this article, to learn more about articles like this you can click here. Thank you for reading.