Simply Merge Sort

Have you ever tried to sort a messy pile of papers or cards?
What if you could break that pile into small parts, sort each part, and then put them back together neatly?

That’s exactly what Merge Sort does.

What is Merge Sort?

Merge Sort is a sorting algorithm that follows a strategy called Divide and Conquer.It sort a list by dividing it into smaller pieces, sorting those pieces, and then joining them back in the right order.

Why Use Merge Sort?

• It’s faster than simple algorithms like Bubble Sort or Insertion Sort.
• It performs well on large datasets.
• It is predictable and always takes the same amount of time for the same size input.
• It has consistent performance regardless of how the input is arranged.

Time Complexity: Best Case, Average Case, Worst Case — O(n log n)

Get Farhan Mahmood’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Space Complexity: O(n)

How It Works (Step-by-Step): (We are going with recursion)

sort this array of numbers arr = [5,6,9,8,4,1,2,5,3,6,7,44,5,66,8] iusing merge sort.

Look into the flow chart carefully,

• Pink represents the initial unsorted array
• Blue shows the first level of splitting
• Green indicates the second level of splitting
• Yellow shows the smallest subarrays
• Red represents the final sorted result.

Let solve this using python

def merge_sort(arr):
    "Main function that splits the array and calls merge"
  
    # Base case: if the array has 0 or 1 element, it is already sorted
    if len(arr)<=1: 
        return arr # Return the array as it is
    
    mid = len(arr)//2 # Find the middle index of the array
    left = arr[:mid] # Left half from index 0 to mid-1
    right = arr[mid:] # Right half from mid to end
    
    # Recursively sort both halves
    sorted_left = merge_sort(left) 
    sorted_right = merge_sort(right)

    # Merge the two sorted halves and return the result
    return merge(sorted_left, sorted_right)

def merge(left, right):
    "Function to merge two sorted lists into one sorted list"

    result = []
    left_index = right_index = 0

    # Merge the two halves while comparing elements
    while len(left)>left_index and len(right)>right_index:
        if left[left_index]<right[right_index]:
            result.append(left[left_index])
            left_index += 1
        else:
            result.append(right[right_index])
            right_index += 1

    # Add remaining elements (if any)
    result.extend(left[left_index:])
    result.extend(right[right_index:])

    return result

arr = [5,6,9,8,4,1,2,5,3,6,7,44,5,66,8]
print(merge_sort(arr))

Merge Sort works by recursively breaking your array into smaller and smaller pieces, until you’re left with single elements. Then, it merges those elements back together in sorted order.

At each merge step, it compares values and ensures the smaller ones come first.

So for our array, the final sorted result is:
[1, 2, 3, 4, 5, 5, 5, 6, 6, 7, 8, 44, 66].