Merge sort is considered among the most prominent divide-and-conquer sorting algorithms. It is mainly used to sort the values in any traversable data structure such as a list.
Merge sort algorithm in simple words
- Merge sort works by splitting the given list into two halves, repeating the process on those halves till a single element, and finally merging the two sorted halves together.
- Merge sort algorithm first moves from top to bottom, then dividing the list into smaller and smaller parts until only the separate elements remain.
- From there, it moves back toward an upward direction, ensuring that the merging lists are sorted.
Now it’s time for its implementation in Python code 🙂
Python Code for Merge Sort
# Merge Sort Published on Freshlybuilt.com #Function for merge operation def merge(left_half, right_half): result_lst =  while len(left_half) != 0 and len(right_half) != 0: if left_half < right_half: result_lst.append(left_half) left_half.remove(left_half) else: result_lst.append(right_half) right_half.remove(right_half) result_lst += right_half if len(left_half) == 0 else left_half print("Current result list value : ", result_lst) return result_lst # Function for dividing an list and return final sorted list def merge_sort(unsorted_list): if len(unsorted_list) <= 1: return unsorted_list # Find the middle point and divide it middle = len(unsorted_list) // 2 left_list = unsorted_list[:middle] right_list = unsorted_list[middle:] left_list = merge_sort(left_list) right_list = merge_sort(right_list) return list(merge(left_list, right_list)) def main(): lst = [8, 17, 3, 9] print("Initial Unsorted List:", lst) print("After Sorting:", merge_sort(lst)) if __name__ == "__main__": main()
Initial Unsorted List: [8, 17, 3, 9]After Sorting: [3, 8, 9, 17]
Flowchart For Merge Sort in Python
As you have read the code, Now it time for flowchart of Merge Sort.
Now its, Time for short Youtube on Merge sort in Python code 🙂
Some Facts about Merge sort
|Best Case Time Complexity||O(nLogn)|
|Average Case Time Complexity||O(nLogn)|
|Worst Case Time Complexity||O(nLogn)|
|Algorithmic Paradigm||Divide and Conquer|
|Sorting in Place||Not in typical implementation|
This case becomes different mainly due to the difference in memory allocation of arrays and linked lists. In a linked list, nodes may not be adjacent in memory unlike to array. In the linked list, we can insert items in the middle in O(1) extra space and O(1) time, but the same condition doesn’t work fine on an array. Therefore merge operation of merge sort can be implemented without extra space for linked lists.
In the case of arrays, we can do random access as elements are contiguous in memory. Let us say we have an integer (4-byte) array A and let the address of A be x then to access A[i], we can directly access the memory at (x + i*4). Unlike arrays, we can not do random access on the linked list. Quick Sort requires a lot of this kind of access. In the linked list to access i’th index, we have to travel each and every node from the head to i’th node as we don’t have a contiguous block of memory. Therefore, the overhead increases for quicksort. Merge sort accesses data sequentially and the need for random access is low.
Now our merge sort post comes to end. Hope you have enjoy it. If you do then please like and share my post in your friend circle.