Merge Sort Algorithm | Stable Divide and Conquer Sorting Method

Description

Merge Sort is a divide-and-conquer algorithm that recursively breaks down a problem into smaller, more manageable subproblems until they become simple enough to solve directly. The solutions to the subproblems are then combined to solve the original problem.

How It Works

Divide the unsorted array into n subarrays, each containing one element (a list of one element is considered sorted)
Repeatedly merge subarrays to produce new sorted subarrays until there is only one subarray remaining
This will be the sorted array

Visualization

Speed:

Click Start to begin visualization

Implementation


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

def mergesort(arr):
    if len(arr) <= 1:
        return arr
        
    mid = len(arr) // 2
    left = mergesort(arr[:mid])
    right = mergesort(arr[mid:])
    
    return merge(left, right)

# Example usage
if __name__ == "__main__":
    arr = [64, 34, 25, 12, 22, 11, 90]
    print("Original array:", arr)
    sorted_arr = mergesort(arr)
    print("Sorted array:", sorted_arr)


#include <iostream>
#include <vector>

class MergeSort {
private:
    static std::vector<int> merge(const std::vector<int>& left, const std::vector<int>& right) {
        std::vector<int> result;
        size_t i = 0, j = 0;
        
        while (i < left.size() && j < right.size()) {
            if (left[i] <= right[j]) {
                result.push_back(left[i++]);
            } else {
                result.push_back(right[j++]);
            }
        }
        
        result.insert(result.end(), left.begin() + i, left.end());
        result.insert(result.end(), right.begin() + j, right.end());
        return result;
    }
    
public:
    static std::vector<int> sort(const std::vector<int>& arr) {
        if (arr.size() <= 1) return arr;
        
        size_t mid = arr.size() / 2;
        std::vector<int> left(arr.begin(), arr.begin() + mid);
        std::vector<int> right(arr.begin() + mid, arr.end());
        
        left = sort(left);
        right = sort(right);
        
        return merge(left, right);
    }
};

// Example usage
int main() {
    std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    
    std::cout << "Original array: ";
    for (int num : arr) std::cout << num << " ";
    std::cout << std::endl;
    
    arr = MergeSort::sort(arr);
    
    std::cout << "Sorted array: ";
    for (int num : arr) std::cout << num << " ";
    std::cout << std::endl;
    
    return 0;
}


public class MergeSort
{
    private static int[] Merge(int[] left, int[] right)
    {
        int[] result = new int[left.Length + right.Length];
        int i = 0, j = 0, k = 0;
        
        while (i < left.Length && j < right.Length)
        {
            if (left[i] <= right[j])
                result[k++] = left[i++];
            else
                result[k++] = right[j++];
        }
        
        while (i < left.Length)
            result[k++] = left[i++];
            
        while (j < right.Length)
            result[k++] = right[j++];
            
        return result;
    }
    
    public static int[] Sort(int[] arr)
    {
        if (arr.Length <= 1)
            return arr;
            
        int mid = arr.Length / 2;
        int[] left = new int[mid];
        int[] right = new int[arr.Length - mid];
        
        Array.Copy(arr, 0, left, 0, mid);
        Array.Copy(arr, mid, right, 0, arr.Length - mid);
        
        left = Sort(left);
        right = Sort(right);
        
        return Merge(left, right);
    }
    
    // Example usage
    public static void Main(string[] args)
    {
        int[] arr = { 64, 34, 25, 12, 22, 11, 90 };
        
        Console.WriteLine("Original array: " + string.Join(" ", arr));
        arr = Sort(arr);
        Console.WriteLine("Sorted array: " + string.Join(" ", arr));
    }
}

Quick Info

Merge Sort

Description

How It Works

Visualization

Implementation

Advantages and Disadvantages

Advantages

Disadvantages