🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.
▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube
▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube
1. Introduction
In this blog post, we will learn how to write a Python program to implement merge sort on a list.
Merge Sort is a classic divide-and-conquer sorting algorithm. It works by dividing the unsorted list into n sub-lists, each containing one element (which is considered sorted). Then, it repeatedly merges these sub-lists to produce new sorted sub-lists until there is only one sub-list left. This final sub-list is the sorted list.
2. Program Overview
In this program, we will:
1. Define a function to merge two halves of a list.
2. Define the main mergeSort function that divides the list and sorts each half.
3. Test the merge sort implementation on a sample list.
3. Code Program
def mergeSort(arr):
# Base case: If the array has one or zero elements, it's already sorted.
if len(arr) <= 1:
return arr
# Split the list in half
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
# Recursively sort both halves
left_half = mergeSort(left_half)
right_half = mergeSort(right_half)
# Merge the sorted halves
merged = []
i = j = 0
# Merge while there are elements in either left or right
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
merged.append(left_half[i])
i += 1
else:
merged.append(right_half[j])
j += 1
# Add the remaining elements if any
while i < len(left_half):
merged.append(left_half[i])
i += 1
while j < len(right_half):
merged.append(right_half[j])
j += 1
return merged
# Test the function
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = mergeSort(arr)
print("Original Array:", arr)
print("Sorted Array:", sorted_arr)
Output:
Original Array: [38, 27, 43, 3, 9, 82, 10] Sorted Array: [3, 9, 10, 27, 38, 43, 82]
4. Step By Step Explanation
1. The list is recursively divided in half until we get sub-lists with only one element.
2. We then merge these sub-lists (which are sorted) to produce larger, fully sorted sub-lists.
3. This process is repeated until we merge all sub-lists into one single sorted list.
My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:
Build REST APIs with Spring Boot 4, Spring Security 7, and JWT
![[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25](https://img-c.udemycdn.com/course/750x422/6852721_b512_2.jpg "[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25")
[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25
ChatGPT + Generative AI + Prompt Engineering for Beginners
Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)
Available in Udemy for Business
Building Real-Time REST APIs with Spring Boot - Blog App
Available in Udemy for Business
Building Microservices with Spring Boot and Spring Cloud
Available in Udemy for Business
Java Full-Stack Developer Course with Spring Boot and React JS
Available in Udemy for Business
Build 5 Spring Boot Projects with Java: Line-by-Line Coding
Testing Spring Boot Application with JUnit and Mockito
Available in Udemy for Business
Spring Boot Thymeleaf Real-Time Web Application - Blog App
Available in Udemy for Business
Master Spring Data JPA with Hibernate
Available in Udemy for Business
Spring Boot + Apache Kafka Course - The Practical Guide
Available in Udemy for Business
Comments
Post a Comment
Leave Comment