Merge Sort Algorithm

Merge Sort Algorithm

Merge sort is a divide-and-conquer algorithm that recursively divides the input array into smaller sublists until each sublist contains a single element. It then merges these sublists to produce a sorted array. It is efficient and stable, making it suitable for large datasets.

How Merge Sort Works

1. Divide: Split the unsorted list into two approximately equal halves.
2. Recursive Division: Keep dividing each smaller sublist until you end up with singular lists.
3. Merge: Compare these singular lists with each other and merge them back together in order.
4. Repeat: Continue merging the sorted sublists until you have one sorted list left.

Pseudocode

Here is the pseudocode for a bubble sort algorithm:

BEGIN
    FUNCTION merge_sort(list)
        IF length(list) <= 1 THEN
            RETURN list
        ENDIF

        SET middle = length(list) / 2
        SET left_half = list[0:middle]
        SET right_half = list[middle:length(list)]

        left_half = merge_sort(left_half)
        right_half = merge_sort(right_half)

        RETURN merge(left_half, right_half)
    ENDFUNCTION

    FUNCTION merge(left, right)
        SET result = []
        WHILE left and right are not empty DO
            IF first(left) <= first(right) THEN
                APPEND first(left) to result
                REMOVE first(left) from left
            ELSE
                APPEND first(right) to result
                REMOVE first(right) from right
            ENDIF
        ENDWHILE

        APPEND any remaining elements of left to result
        APPEND any remaining elements of right to result

        RETURN result
    ENDFUNCTION
END

Example in Python

Below is an example implementation of bubble sort in Python:

def merge_sort(lst):
    if len(lst) <= 1:
        return lst

    mid = len(lst) // 2
    left_half = lst[:mid]
    right_half = lst[mid:]

    left_sorted = merge_sort(left_half)
    right_sorted = merge_sort(right_half)

    return merge(left_sorted, right_sorted)

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])

    return result

# Example usage
numbers = [38, 27, 43, 3, 9, 82, 10]
sorted_numbers = merge_sort(numbers)
print("Sorted list is:", sorted_numbers)

Key Points

Use Cases: Suitable for large datasets and for applications where stability is important (i.e., maintaining the relative order of equal elements).

Advantages

• Efficient for large datasets.
• Stable sort (preserves the relative order of equal elements).
• Parallelizable (can be easily divided and executed in parallel).

Disadvantages

• Requires additional memory proportional to the size of the input list.
• More complex to implement compared to simpler algorithms like bubble sort.

• Time Complexity: O(n log n), where n is the number of elements in the list.
• Space Complexity: O(n), as it requires additional memory for merging.