Data we save or get from an application could occasionally be poorly or randomly organized. We might need to reorganize the data to handle or utilize it properly. To arrange data, computer scientists have developed a variety of sorting algorithms over time.
In this post, we'll examine the merge sort algorithm, provide an introduction to the divide-and-conquer strategy for addressing problems, explain its operations and principles, and implement it in Python. We'll also contrast how quickly it can sort a list of objects.
Based on the Divide and Conquer strategy, Merge Sort is one of the most effective and popular sorting algorithms. An unsorted array is recursively divided into smaller subarrays until each subarray has a single element. A fully sorted array is produced by merging these smaller subarrays back together in sorted order.
Merge Sort is a great option for sorting big datasets since it ensures a time complexity of O(n log n) in the best, average, and worst circumstances, unlike straightforward sorting algorithms like Bubble Sort or Selection Sort. Merge Sort needs more memory because it generates temporary arrays during the merging operation, but its reliable performance and stability make it a well-liked method in practical applications.
Recursion may be used to build Merge Sort in Python, making it an excellent illustration of divide-and-conquer tactics, recursive programming, and effective algorithm design. In order to help you grasp the algorithm, you will study how Merge Sort operates, comprehend how it is implemented in Python step-by-step, evaluate its time and space complexity, and witness a real-world application.
What Are Divide-and-Conquer Algorithms?
Divide-and-conquer methods can be applied recursively, meaning the main problem is broken down into related subproblems before being solved. The solutions to the smaller difficulties are combined to provide the overall solution to the bigger issue.
The divide-and-conquer method of algorithm design has three key parts:
Divide - continuously breaks down the larger problem into smaller subproblems.
Conquer - solves each subproblem by using any function.
Combine - merges all the solutions of each subproblem and makes a single unified solution, which becomes the solution to the starting problem.
What Is Merge Sort?
To efficiently sort the items in a list, the merge sort method uses the divide-and-conquer algorithm paradigm. The foundation of the merge sort process is to divide the list in half, then continually separate the new half into its individual parts. Following a comparison of each component separately, the combined results are combined to create the final sorted list.
Merge Sort is a comparison-based sorting algorithm that effectively sorts elements by using the Divide and Conquer strategy. Merge Sort continually splits the array into two smaller halves until each subarray has just one element, as opposed to sorting the entire array at once. The method then combines these subarrays back together in the proper sequence to create a fully sorted array because a single element has already been sorted.
With a time complexity of O(n log n) in the best, average, and worst scenarios, Merge Sort is renowned for its consistent performance. Additionally, it maintains the relative order of elements with equal values because it is a stable sorting algorithm. Due to its efficiency and dependability, Merge Sort is frequently used for sorting huge datasets, linked lists, and external data stored on drives, even if the merging procedure necessitates additional RAM.
Implementation of Merge Sort in Python
The merge sort method is implemented using a two-part strategy.
The split phase of the divide-and-conquer paradigm will be carried out in the first portion. This section's implementation of the code will separate the initial list into more manageable parts. Only when each separated component can no longer be broken down will the original list split come to an end.
An example of the algorithm's first step may be shown below.
Step 1: Top-to-Bottom Approach
def merge_sort(list):
# 1. Store the length of the list in the length container.
length = len(list)
# 2. if length is equal to 1 then return original list.
if length == 1:
return list
# 3. Identify the list midpoint and break the list into two part one is left part and second is right part.
mid = length // 2
# 4.A partitioned section of the list is supplied as an argument to the merge_sort function, which makes sure that each part is split into its individual parts.
left_part = merge_sort(list[:mid])
right_part = merge_sort(list[mid:])
# 5. The merge_sort function produces a list with sorted left and right part as its output.
return merge(left_part,right_part)
Step 1.1: Define the Merge Sort Function
def merge_sort(list):
The merge_sort() function, which accepts a list as input, is defined at this line. This function's goal is to use the Merge Sort algorithm to sort the list's elements.
Step 1.2: Find the Length of the List
length = len(list)
The total number of elements in the list is determined using the len() method. The length is kept in the length variable, which aids in figuring out whether the list has to be further divided.
Step 1.3: Check the Base Case
if length == 1:
return list
The recursive algorithm's base case is this. The function just returns the list without making any more recursive calls if there is only one entry in the list, indicating that it has already been sorted.
Step 1.4: Find the Midpoint of the List
mid = length // 2
The list is split into two equal (or nearly equal) halves at the middle. By performing integer division, the // operator guarantees that the midpoint is always an integer.
Step 1.5: Divide the List into Two Halves
left_part = merge_sort(list[:mid])
right_part = merge_sort(list[mid:])
The list is divided into two smaller sublists:
list[:mid] creates the left half.
list[mid:] creates the right half.
The merge_sort() function is then called recursively on both halves. This process continues until every sublist contains only one element.
Step 1.6: Merge the Sorted Halves
return merge(left_part, right_part)
The left and right halves are already sorted when the recursive calls are complete. These two sorted halves are combined into a single sorted list using the merge() method.
Step 2: Bottom-to-Top Approach
# 1. take the two list as input and return the sorted list as output
def merge(left, right):
# 2. Initialize an empty list as answer that will be store the sorted elements
# Initialize two variables i and j which are used pointers when iterating through the lists.
answer = []
i = j = 0
# 3. Executes the while loop if both pointers i and j are less than the length of the left and right lists
while i < len(left) and j < len(right):
# 4. Compare the elements at every position of both lists during each iteration
if left[i] < right[j]:
# 5. if the left list value less then right list value , then append the left list value in the answer.
answer.append(left[i])
# 6. increase or move the pointer by 1.
i += 1
else:
#7. append the right list value in the answer if right list value is lesser then tha left list value.
answer.append(right[j])
#8. and move the j pointer by 1
j += 1
# 9. the remaining value of the both left and right list is picked from the current pointer to the end and extend to the answer
answer.extend(left[i:])
answer.extend(right[j:])
#10.return the answer(that is sorted list)
return answer
Step 2.1: Define the merge() Function
def merge(left, right):
The merge() function creates a single sorted list by combining two previously sorted lists (left and right) as input.
Step 2.2: Initialize Variables
answer = []
i = j = 0
The combined sorted elements are stored in an empty list called answer. The initial values of the two pointers, i and j, are 0. The current entry in the left list is tracked by pointer i, and the current element in the right list is tracked by pointer j.
Step 2.3: Compare Elements from Both Lists
while i < len(left) and j < len(right):
As long as both lists contain unprocessed elements, the while loop will continue. The algorithm compares the current elements that i and j point to on each iteration.
Step 2.4: Add the Smaller Element to the Result
if left[i] < right[j]:
answer.append(left[i])
i += 1
else:
answer.append(right[j])
j += 1
The left pointer (i) advances to the following element if the current element in the left list is smaller and is added to the answer list. If not, the right pointer (j) is increased, and the current element from the right list is appended. This procedure guarantees that the components are included in the answer in the correct order.
Step 2.5: Append the Remaining Elements and Return the Result
answer.extend(left[i:])
answer.extend(right[j:])
return answer
The remaining items from the other list have already been sorted once one of the lists has finished processing. The extend() technique is used to add these components to the answer list. Lastly, the fully combined and sorted list is returned by the function.
Step 3: Create Input List Function
def merge_sort_print():
input = [5,48,95,74,65,32,56,58,65,32,8,6,4,5,25,64]
print(input)
sorted_list = merge_sort(input)
print(sorted_list)
merge_sort_print()
The Merge Sort algorithm's operation is illustrated via the merge_sort_print() function. Initially, an unsorted list of integers is created and printed to the console. The list is then sorted in ascending order using the merge_sort() function, and the outcome is saved in the sorted_list variable. You can compare the original and sorted outputs after it prints the sorted list. The function is executed, and the results are shown by the last statement, merge_sort_print().
Merge Sort Code In Python
Now that you know how the Merge Sort algorithm operates, let's put it into practice in Python. The input list is continuously divided into smaller sublists by the implementation using a recursive technique until each sublist has just one element. The final sorted list is created by merging the sorted sublists back together in the proper order when the division operation is finished.
The Merge Sort algorithm's full implementation is shown in the Python program that follows. It contains a merge() function to combine the sorted sublists into a single sorted list and a merge_sort() method to split the list recursively.
def merge_sort(list):
length = len(list)
if length == 1:
return list
mid = length // 2
left_part = merge_sort(list[:mid])
right_part = merge_sort(list[mid:])
return merge(left_part, right_part)
def merge(left, right):
answer = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
answer.append(left[i])
i += 1
else:
answer.append(right[j])
j += 1
answer.extend(left[i:])
answer.extend(right[j:])
return answer
def merge_sort_print():
input1 = [5,48,95,74,65,32,56,58,65,32,8,6,4,5,25,64]
print(input1)
sorted_list = merge_sort(input1)
print(sorted_list)
merge_sort_print()
Step 1: Define the merge_sort() Function
The algorithm's primary function is merge_sort(). It initially determines the input list's length and verifies the base case. The function returns the list right away if there is only one element because it has already been sorted. If not, the midpoint is used to split the list in half.
def merge_sort(list):
length = len(list)
if length == 1:
return list
mid = length // 2
left_part = merge_sort(list[:mid])
right_part = merge_sort(list[mid:])
Step 2: Recursively Divide the List
The function recursively calls itself for both the left and right half of the list. This method continues until every sublist has only one element. This is the Divide step in the Divide and Conquer method.
left_part = merge_sort(list[:mid])
right_part = merge_sort(list[mid:])
Step 3: Merge the Sorted Sublists
The merge() function merges the two parts into a single sorted list after they have been sorted. It adds the smaller element to a new list after comparing each element individually from the left and right sublists.
return merge(left_part, right_part)
The merge() function:
def merge(left, right):
answer = []
i = j = 0
uses two pointers (i and j) to traverse the left and right sublists efficiently.
Step 4: Add Remaining Elements
The extend() method is used to add any entries from the other sublist to the result after one of the sublists has finished processing. These components can be directly attached because they have already been sorted.
answer.extend(left[i:])
answer.extend(right[j:])
return answer
Step 5: Execute the Program
An unsorted list is created, shown, sorted using the merge_sort() function, and the sorted result is printed by the merge_sort_print() function.
def merge_sort_print():
input1 = [5,48,95,74,65,32,56,58,65,32,8,6,4,5,25,64]
print(input1)
sorted_list = merge_sort(input1)
print(sorted_list)
merge_sort_print()
When the program runs, it prints the original list first and then shows the list after the Merge Sort algorithm has sorted it in ascending order.
Output:
Merge Sort Time Complexity
In the best, medium, and worst scenarios, Merge Sort's time complexity is O(n log n). The fact that Merge Sort performs consistently regardless of the arrangement of the input data is one of its key features.
Best Case: (n log n)
When the input list is already sorted, this is the ideal scenario. Merge Sort splits the list into smaller sublists and then combines them back together even though the elements are in the right order. The time complexity is still O(n log n) because it cannot establish that the list has already been sorted without completing these steps.
Average Case: O(n log n)
The elements in the list are often arranged randomly. Merge Sort merges the sorted sublists after splitting the list in half recursively. The total time complexity is O(n log n) as the list is divided log n times and each merging operation processes all n members.
Worst Case: (n log n)
The worst scenario is when the elements are placed in any order that necessitates the greatest number of comparisons during the merging process, or in reverse order. Merge Sort carries out the same number of divisions and merging operations even in this scenario. As a result, O(n log n) is also the worst-case time complexity.
Merge Sort Space Complexity
Merge Sort has an O(n) space complexity. This is due to the fact that while merging the split sublists back together, Merge Sort generates new temporary arrays (or lists). In contrast to certain in-place sorting algorithms, Merge Sort needs additional memory to hold these transient components while sorting.
Application of Merge Sort
Because of its known time complexity, stability, and effective performance, merge sort is frequently employed in computer science. Some of the most popular uses for Merge Sort are listed below:
1. Sorting Large Datasets
Because it ensures a time complexity of O(n log n), regardless of whether the data is previously sorted or entirely random, merge sort is a great option for sorting big collections of data.
2. External Sorting
Merge Sort is frequently used for external sorting when there is too much data to fit in the computer's main memory. It divides disk-stored data into smaller pieces, sorts each piece independently, and then combines the sorted files.
3. Linked List Sorting
One of the finest algorithms for sorting linked lists is merge sort. Merge Sort is a better option since linked lists may be split and merged effectively without the need for extra element moving, unlike arrays.
4. Stable Sorting Applications
Because Merge Sort maintains the relative order of elements with equal values, it is a stable sorting method. This makes it helpful in applications like sorting employee records, student records, or transaction data when it's crucial to preserve the original order of duplicate records.
5. Divide and Conquer Problems
Because Merge Sort exemplifies the Divide and Conquer strategy, it can be used to solve a variety of algorithmic issues that require recursively decomposing a problem into smaller subproblems.
Advantages of Merge Sort
In the best, medium, and worst scenarios, Merge Sort is an effective and dependable sorting algorithm that ensures a time complexity of O(n log n). Because it maintains the relative order of equal elements, it is a stable sorting algorithm. It is a common option in real-world applications because it is especially well suited for sorting big datasets, linked lists, and data kept on external storage devices.
Disadvantages of Merge Sort
The primary flaw in Merge Sort is that, to hold temporary arrays during the merging operation, O(n) more memory is needed. Compared to methods like Quick Sort or Heap Sort, it uses more memory because it is not an in-place sorting algorithm. Additionally, Merge Sort is less effective for sorting very tiny datasets due to the overhead introduced by the recursive function calls.
Conclusion
Based on the Divide and Conquer strategy, Merge Sort is one of the most effective and popular sorting algorithms. To create a fully sorted list, it recursively splits a list into smaller sublists, sorts them, and then combines them back together. Merge Sort is a great option for sorting big datasets and linked lists because of its steady sorting behavior and guaranteed O(n log n) time complexity in all scenarios. Its continuous performance and dependability make it a useful algorithm for both academic learning and practical applications, even if it consumes more memory during the merging process. A solid basis for learning other sophisticated algorithms and recursive problem-solving strategies is also provided by comprehending Merge Sort.
Next Steps
- Explore the Bucket Sort algorithm.
- Explore Selection Sort Algorithm.
- Explore Quick Sort Algorithm.
- Explore Heap sort Algorithm.
- Explore Bubble Sort Algorithm.
Top comments (1)
You should take advantage of ordered runs, dear Jon Snow.