Merge Sort Algorithm in Python

1. Introduction

Merge Sort is a divide-and-conquer algorithm that works by recursively breaking down a list into two halves until each sublist contains a single element, and then merging those sublists in a manner that results into a sorted list.

2. Implementation Steps

1. Divide the unsorted list into n sublists, each containing one element (a list of one element is considered sorted).

2. Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining.

3. Implementation in Python

def merge_sort(arr):
    # Base condition to exit the recursive call
    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 = merge_sort(left_half)
    right_half = merge_sort(right_half)
    # Merge the sorted halves
    merged = []
    i = 0
    j = 0
    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
    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
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print(sorted_arr)

Output:

[3, 9, 10, 27, 38, 43, 82]

Explanation:

1. The function merge_sort starts by checking if the length of arr is less than or equal to 1. If it is, the list is already sorted, and we return it as-is.

2. We then split the list into two halves using the middle index. These halves are left_half and right_half.

3. We recursively sort both halves by calling merge_sort on them.

4. Once both halves are sorted, we merge them together in sorted order. We use two pointers i and j to track our position in the left_half and right_half, respectively.

5. We compare the current elements of left_half and right_half, append the smaller element to the merged list, and move the pointer of that half forward.

6. After one of the halves is exhausted, we append the remaining elements of the other half to merged.

7. Finally, the merged sorted list is returned.

Related Algorithms in Python


Comments