Skip to content
Menu
Portfolio
  • Personal Projects
  • Assignments
  • Algorithms
  • Notes
  • Home
Portfolio

Merge Sort

Posted on July 11, 2022February 7, 2025

Method:

  • The Merge Sort algorithm is a sorting algorithm that is considered as an example of the divide and conquer strategy. So, in this algorithm, the array is initially divided into two equal halves and then they are combined in a sorted manner. We can think of it as a recursive algorithm that continuously splits the array in half until it cannot be further divided. This means that if the array becomes empty or has only one element left, the dividing will stop, i.e. it is the base case to stop the recursion. If the array has multiple elements, we split the array into halves and recursively invoke the merge sort on each of the halves. Finally, when both the halves are sorted, the merge operation is applied. Merge operation is the process of taking two smaller sorted arrays and combining them to eventually make a larger one.

C++ Template for Merge Sort function:

void merge_sort(int A[], int l, int r)
{
    // only one element
    if (l >= r) return;
    
    int mid = l + r >> 1;
    
    // Recursively sort on the left and right.
    merge_sort(A, l, mid);
    merge_sort(A, mid + 1, r);

    // Merge two separate lists 
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (A[i] <= A[j]) tmp[k ++] = A[i ++];
        else tmp[k ++] = A[j ++];

    // add all remaining elements
    while (i <= mid) tmp[k ++] = A[i ++];
    while (j <= r) tmp[k ++] = A[j ++];

    // move elements from tmp to original array
    for (i = l, j = 0; i <= r; i++, j++) 
        A[i] = tmp[j];
}

Idea:

  1. Find median element. int mid = l + r >> 1;
  2. Recursively sort on the left and right.
  3. Merge two separate lists.

Python Template for Merge Sort function:

def merge_sort(A, l, r):
    # Only one element
    if l >= r:
        return
    
    mid = (l + r) // 2
    
    # Recursively sort on the left and right
    merge_sort(A, l, mid)
    merge_sort(A, mid + 1, r)
    
    # Merge two separate lists
    tmp = []
    i, j = l, mid + 1
    while i <= mid and j <= r:
        if A[i] <= A[j]:
            tmp.append(A[i])
            i += 1
        else:
            tmp.append(A[j])
            j += 1
    
    # Add all remaining elements
    while i <= mid:
        tmp.append(A[i])
        i += 1
    while j <= r:
        tmp.append(A[j])
        j += 1
    
    # Move elements from tmp to original array
    for i in range(len(tmp)):
        A[l + i] = tmp[i]

Other:

  • Sorting And Searching Algorithms – Time Complexities Cheat Sheet

Reference:

  • GeeksforGeeks
  • Zhihu
  • AcWing

CATEGORIES

  • Personal Projects
  • Notes
  • Algorithms

  • University of Maryland
  • CMSC426 - Computer Vision
  • CMSC320 - Introduction to Data Science
  • CMSC330 - Organization of Programming Languages
  • CMSC216 - Introduction to Computer Systems
©2025 Portfolio | WordPress Theme by Superbthemes.com