Exploring Time and Space Complexity of Merge Sort

This article is a complementary resource to the DSA with Python and DSA with C++ courses.

Exploring Time and Space Complexity of Merge Sort

Merge sort is a comparison-based divide-and-conquer sorting algorithm that works by recursively dividing the array into halves, sorting each half, and then merging them back together.

Python

Java

C++

def merge_sort(arr):
    # If the array has 1 or no elements,
    # return it as it's already sorted
    if len(arr) <= 1:
        return arr

    # Divide the array into two halves
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])  # Recursively sort the left half
    right = merge_sort(arr[mid:])  # Recursively sort the right half

    # Merge the sorted halves and return the result.
    return merge(left, right)

def merge(left, right):
    # Create a result array to store merged elements
    result = []
    # Initialize pointers for the left and right arrays
    i = j = 0

    # Compare elements from both arrays
    # and add the smaller one to the result
    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 from the left array to the result
    result.extend(left[i:])
    # Add remaining elements from the right array to the result
    result.extend(right[j:])

    # Return the merged and sorted array
    return result

template<typename T>
std::vector<T> merge_sort(std::vector<T>& arr) {
    // If the array has 1 or no elements,
    // return it as it is already sorted
    if(arr.size() <= 1) return arr;

    // Find the midpoint of the array
    int mid = arr.size() / 2;

    // Divide the array into left and right halves
    std::vector<T> left(arr.begin(), arr.begin() + mid);
    std::vector<T> right(arr.begin() + mid, arr.end());

    // Recursively sort the left half
    left = merge_sort(left);
    // Recursively sort the right half.
    right = merge_sort(right);

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

template<typename T>
std::vector<T> merge(std::vector<T>& left, std::vector<T>& right) {
    // Initialize the result vector to store the merged elements
    std::vector<T> result;
    // Initialize pointers for the left and right vectors
    int i = 0, j = 0;

    // Compare elements from both vectors
    // and add the smaller one to the result
    while(i < left.size() && j < right.size()) {
        if(left[i] < right[j]) {
            result.push_back(left[i]);
            i++;
        }
        else {
            result.push_back(right[j]);
            j++;
        }
    }

    // Append the remaining elements from the left vector to the result
    result.insert(result.end(), left.begin() + i, left.end());
    // Append the remaining elements from the right vector to the result
    result.insert(result.end(), right.begin() + j, right.end());

    // Return the merged and sorted vector
    return result;
}

Average Case Time Complexity: O(n logn)

Merge sort involves two main operations:

Dividing the Array: Each step splits the array into two halves.
Merging Sorted Arrays: After sorting, it merges the smaller arrays into a larger sorted array.

The division occurs recursively, splitting the array into halves every call. So, the recursion depth is O(logn).

Each merging step involves comparing elements to merge two sorted subarrays into a single sorted array. If there are n elements in total, merging all subarrays at a given level takes O(n) time.

Thus, the total time complexity is:

O(logn) × O(n) = O(nlogn)

Comparing the Number of Operations Required for Different Input Sizes in Merge Sort

Space Complexity of Merge Sort: O(n)

Merge sort is not an in-place sorting algorithm—it requires additional space to store the left and right subarrays during the merge process.

Thus, the space complexity is O(n) as it needs extra space to hold temporary arrays during the merging step.

Summary: Time and Space Complexity

Time Complexity	`O(n logn)`
Space Complexity	`O(n)`

When to Use Merge Sort?

Merge sort is particularly useful when stable sorting is required, and when the data is too large to fit into memory and needs to be processed externally (such as in external sorting).

When to Use:

Large Datasets: Merge sort performs consistently with O(n logn) time complexity, making it suitable for sorting large datasets.
Stable Sorting: Merge sort is stable, meaning it preserves the relative order of equal elements.
External Sorting: Merge sort works by dividing the array into manageable parts and merging them. It is ideal for cases where data is too large to fit into memory and must be stored externally (e.g., sorting large databases or files).

When to Avoid:

Memory Constraints: Merge sort requires O(n) additional space, which makes it unsuitable for scenarios where memory is limited.
Small Datasets: For small datasets, simpler algorithms such as Insertion Sort or Quick Sort may be more efficient due to their lower overhead.