Skip to content

Merge Sort Algorithm

Algorithm Introduction

Merge sort is an efficient, divide-and-conquer based sorting algorithm. It divides the array into two halves, sorts each half recursively, and then merges the sorted halves. Merge sort is a stable sorting algorithm suitable for large datasets.

Algorithm Steps

  1. Divide the unsorted array into two equal-sized subarrays
  2. Recursively sort each subarray
  3. Merge the two sorted subarrays into one sorted array

Code Implementation

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

    # Divide the array
    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 two sorted halves
    return merge(left_half, right_half)

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

    # Compare elements from both arrays and merge
    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

    # Add remaining elements
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# Test
arr = [5, 3, 8, 4, 2]
sorted_arr = merge_sort(arr)
print("Sorted array:", sorted_arr)

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        int[] sorted = mergeSort(arr);
        System.out.println("Sorted array:");
        for (int num : sorted) {
            System.out.print(num + " ");
        }
    }

    public static int[] mergeSort(int[] arr) {
        if (arr.length <= 1) {
            return arr;
        }

        // Divide the array
        int mid = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);

        // Recursively sort both halves
        left = mergeSort(left);
        right = mergeSort(right);

        // Merge the two sorted halves
        return merge(left, right);
    }

    private static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0, j = 0, k = 0;

        // Compare elements from both arrays and merge
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result[k++] = left[i++];
            } else {
                result[k++] = right[j++];
            }
        }

        // Add remaining elements
        while (i < left.length) {
            result[k++] = left[i++];
        }

        while (j < right.length) {
            result[k++] = right[j++];
        }

        return result;
    }
}

Complexity Analysis

  • Time Complexity:
  • Worst case: O(n log n)
  • Average case: O(n log n)
  • Best case: O(n log n)
  • Space Complexity: O(n) (requires additional space for merging)

Sorting Example

Let's understand how merge sort works with a concrete example. Suppose we have an array: [5, 3, 8, 4, 2]

Divide Phase

First, we recursively divide the array into smaller subarrays:

First division: 

[5, 3, 8, 4, 2] → [5, 3] and [8, 4, 2]

Second division: 

[5, 3] → [5] and [3]
[8, 4, 2] → [8] and [4, 2]

Third division: 

[4, 2] → [4] and [2]

Now we have single-element subarrays: [5], [3], [8], [4], [2], which are all sorted (single elements are always sorted).

Merge Phase

Next, we start merging these subarrays from bottom up:

First merge: 

[5] and [3] → [3, 5]
[8] and [4, 2] → [4, 2, 8] (need to merge [4] and [2] first)

Merging [4] and [2]: 

Compare 4 and 2: 2 < 4, take 2
Result: [2]
Remaining: [4]
Final result: [2, 4]

Then merge [8] and [2, 4]: 

Compare 8 and 2: 2 < 8, take 2
Result: [2]
Compare 8 and 4: 4 < 8, take 4
Result: [2, 4]
Remaining: [8]
Final result: [2, 4, 8]

Second merge: 

[3, 5] and [2, 4, 8] → [2, 3, 4, 5, 8]

Detailed merge process: 

Compare 3 and 2: 2 < 3, take 2
Result: [2]
Compare 3 and 4: 3 < 4, take 3
Result: [2, 3]
Compare 5 and 4: 4 < 5, take 4
Result: [2, 3, 4]
Compare 5 and 8: 5 < 8, take 5
Result: [2, 3, 4, 5]
Remaining: [8]
Final result: [2, 3, 4, 5, 8]

Final Result

After sorting, we get the sorted array: [2, 3, 4, 5, 8]

This example demonstrates key characteristics of merge sort: - Divide-and-conquer approach: breaking the problem into smaller subproblems - Recursion: applying the same sorting algorithm to subproblems - Merging: combining sorted subarrays into larger sorted arrays - Stability: relative order of equal elements is preserved after sorting

Tree Visualization

Exercises

  1. Implement an in-place version of merge sort to reduce space complexity
  2. Analyze the differences between merge sort implementations for linked lists versus arrays
  3. Compare the performance differences between merge sort and quick sort
  4. Implement a bottom-up, non-recursive version of merge sort


📅 Created 0 days ago ✏️ Updated 0 days ago
daichangya