Close Menu
    Code and Debug
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook X (Twitter) Instagram YouTube WhatsApp
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook Instagram YouTube LinkedIn WhatsApp
    Code and Debug – BlogCode and Debug – Blog
    Code and Debug – BlogCode and Debug – Blog
    Home»Data Structures & Algorithms»Merge Sort Algorithm in Python | Explained
    Data Structures & Algorithms

    Merge Sort Algorithm in Python | Explained

    codeanddebugBy codeanddebug13 June 2025Updated:7 July 2025No Comments5 Mins Read
    Share Facebook Twitter Pinterest LinkedIn Tumblr Reddit Telegram Email
    Merge sort featured image
    Share
    Facebook Twitter LinkedIn Pinterest Email

    Merge Sort is a classic divide-and-conquer sorting technique. It divides the list into two halves, sorts each half recursively, and then merges the two sorted halves.

    So let’s get started with the [Problem Link].

    The major steps are:

    1. Divide: Split the array into two parts.
    2. Conquer: Recursively sort each half.
    3. Combine: Merge the two sorted halves into a single sorted list.

    This approach ensures a guaranteed time complexity of O(nlog⁡n) in the worst, average, and best cases, making Merge Sort a reliable and efficient sorting algorithm, especially for large datasets.

    Contents:
     [show]
    • 1. The merge_sort Function
      • Explanation
    • 2. The merge_array Function
      • Explanation
    • 3. Putting It All Together
    • 4. Dry Run Example
    • 5. Time & Space Complexity
    • 6. Key Takeaways

    1. The merge_sort Function

    def mergeSort(self, arr, l, r):
        if l < r:
            mid = (l + r) // 2
            # Sort first and second halves
            self.mergeSort(arr, l, mid)
            self.mergeSort(arr, mid + 1, r)
            self.merge(arr, l, mid, r)

    Explanation

    1. Base Condition: If the list has 0 or 1 elements, it’s already sorted, so return it as is.
    2. Find Midpoint: Compute mid = len(arr) // 2 to split the array into two nearly equal halves.
    3. Recursive Sort:
      • Recursively call merge_sort(left_half) and merge_sort(right_half).
      • This breaks each subarray further until it reaches the base condition (lists of size 1 or 0).
    4. Merge: After both halves return in sorted form, pass them to merge_array to produce a single, sorted list.

    2. The merge_array Function

    def merge(self, arr, l, mid, r):
        # Create temp arrays
        left = arr[l : mid + 1]
        right = arr[mid + 1 : r + 1]
    
        i = 0
        j = 0
        k = l
    
        # Merge the temp arrays back into arr[l..r]
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                arr[k] = left[i]
                i += 1
            else:
                arr[k] = right[j]
                j += 1
            k += 1
    
        # Copy the remaining elements of left[], if any
        while i < len(left):
            arr[k] = left[i]
            i += 1
            k += 1
    
        # Copy the remaining elements of right[], if any
        while j < len(right):
            arr[k] = right[j]
            j += 1
            k += 1

    Explanation

    1. Initialization: Create an empty list merged. Set pointers i and j to 0, indicating the current index in left and right, respectively.
    2. Compare and Pick:
      • While both i < len(left) and j < len(right), compare left[i] and right[j].
      • Whichever element is smaller, append it to merged and move that pointer forward.
    3. Collect Remaining:
      • If any elements remain in left after one of the lists is exhausted, append all of them.
      • Do the same for the remaining elements in right.
    4. Result: merged now contains a sorted combination of the two sublists.

    Whole Code

    class Solution:
     
        def mergeSort(self, arr, l, r):
            if l < r:
                mid = (l + r) // 2
                # Sort first and second halves
                self.mergeSort(arr, l, mid)
                self.mergeSort(arr, mid + 1, r)
                self.merge(arr, l, mid, r)
        
        def merge(self, arr, l, mid, r):
            # Create temp arrays
            left = arr[l:mid+1]
            right = arr[mid+1:r+1]
            
            i = 0
            j = 0
            k = l
            
            # Merge the temp arrays back into arr[l..r]
            while i < len(left) and j < len(right):
                if left[i] <= right[j]:
                    arr[k] = left[i]
                    i += 1
                else:
                    arr[k] = right[j]
                    j += 1
                k += 1
            
            # Copy the remaining elements of left[], if any
            while i < len(left):
                arr[k] = left[i]
                i += 1
                k += 1
            
            # Copy the remaining elements of right[], if any
            while j < len(right):
                arr[k] = right[j]
                j += 1
                k += 1
    Python

    Also read about the Python Program to Implement Quick Sort Algorithm.

    3. Putting It All Together

    Initial Array:

    arr = [64, 34, 25, 12, 22, 11, 90]
    sorted_arr = merge_sort(arr)
    print(f"Sorted array = {sorted_arr}")

    Call merge_sort(arr):

    1. Splits arr into two halves.
    2. Recursively sorts each half.
    3. Merges them via merge_array.

    Final Output:

    Sorted array = [11, 12, 22, 25, 34, 64, 90]

    4. Dry Run Example

    Let’s dry run a smaller sub-problem: [34, 25, 11].

    1. Split:
      • Left: [34]
      • Right: [25, 11]
    2. Recursively Sort Left: [34] is a single element, so it’s already sorted.
    3. Recursively Sort Right: Split [25, 11] into [25] and [11], both single elements.
      • Merge [25] and [11] → [11, 25].
    4. Merge:
      • Merge [34] and [11, 25].
      • Compare 34 with 11 → take 11. Next compare 34 with 25 → take 25. Finally, take 34.
      • Final merged list: [11, 25, 34].

    5. Time & Space Complexity

    1. Time Complexity:
      • Each time we split the list into two halves and then merge them.
      • The depth of recursion is about log⁡n.
      • At each level, merging all elements takes O(n).
      • Overall time complexity: O(n.log⁡n).
    2. Space Complexity:
      • We allocate extra space for the sublists and for merging.
      • Overall space complexity: O(n) in most implementations.

    6. Key Takeaways

    1. Divide-and-Conquer: Merge Sort systematically splits the array and merges results.
    2. Consistent Performance: It guarantees O(nlog⁡n) even in the worst case.
    3. Stable Sorting: Merge Sort preserves the order of equal elements, which can be advantageous in certain scenarios.

    Requires Extra Space: Unlike in-place sorts, Merge Sort needs additional memory to merge sublists.

    Join our Advance DSA COURSE

    For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.

    Sorting Algorithm
    Share. Facebook Twitter Pinterest LinkedIn Tumblr Email
    Previous ArticleInsertion Sort Algorithm | Explained in Python
    Next Article Quick Sort Algorithm in Python | Explained
    codeanddebug
    • Website

    Related Posts

    Data Structures & Algorithms

    Implement Stack using Queues | Leetcode 225 | Complete Python Code

    26 July 2025
    Data Structures & Algorithms

    Implement Queue Using Array: Complete Guide with Normal and Optimal Solutions

    26 July 2025
    Data Structures & Algorithms

    Implement Stack Using Array | GFG Practice | Complete Guide in Python

    26 July 2025
    Add A Comment
    Leave A Reply Cancel Reply

    Categories
    • Data Structures & Algorithms (159)
      • Beginner (61)
      • Expert (38)
      • Intermediate (60)
    • Uncategorised (1)
    Recent Posts

    Implement Stack using Queues | Leetcode 225 | Complete Python Code

    26 July 2025

    Implement Queue Using Array: Complete Guide with Normal and Optimal Solutions

    26 July 2025

    Implement Stack Using Array | GFG Practice | Complete Guide in Python

    26 July 2025

    Climbing Stairs | Leetcode 70 | Solved using Dynamic Programming

    24 July 2025

    Nth Fibonacci Number | Introduction to Dynamic Programming

    24 July 2025
    Facebook Instagram YouTube LinkedIn WhatsApp
    © 2025 Code and Debug. All rights reserved.

    Type above and press Enter to search. Press Esc to cancel.