DSA69 Merge Sort | Line By Line Code Explanation

DSA69 Merge Sort | Line By Line Code Explanation

Welcome back to Robo Minions. In this video from our AI interview preparation app, we delve into the topic of merge sort using recursion. We'll trace the recursive merge sort code step-by-step. For those following along, the Robo Minions app is available for download on our website. The app allows you to trace code, making it an excellent tool for revising concepts after watching tutorial videos.

I recommend watching this video on a laptop or a full-sized mobile screen for a clearer view while tracing the code with me. After the video, don’t forget to download the app to reinforce your learning.

Let's start tracing the code. An arrow will point to the execution line of the code as we walk through it.

#include <stdio.h>

int main() (
    int data_array[] = {10, 4, 20, 19, 3, 11);
    int size = sizeof(data_array)/sizeof(data_array[0]);
    merge_sort(data_array, 0, size - 1);

    for(int i = 0; i < size; i++) (
        printf("%d ", data_array[i]);
    )
    return 0;
}

void merge_sort(int arr[], int low, int high) (
    if (low < high) {
        int mid = low + (high - low) / 2;
        merge_sort(arr, low, mid);
        merge_sort(arr, mid + 1, high);
        merge(arr, low, mid, high);
    )
}

void merge(int arr[], int low, int mid, int high) (
    int n1 = mid - low + 1;
    int n2 = high - mid;
    int left[n1], right[n2];

    for (int i = 0; i < n1; i++) 
        left[i] = arr[low + i];    
        
    for (int j = 0; j < n2; j++) 
        right[j] = arr[mid + 1 + j];    

    int i = 0, j = 0, k = low;
    while (i < n1 && j < n2) {
        if (left[i] <= right[j]) {
            arr[k] = left[i];
            i++;
        ) else (
            arr[k] = right[j];
            j++;
        )
        k++;
    }

    while (i < n1) (
        arr[k] = left[i];
        i++;
        k++;
    )

    while (j < n2) (
        arr[k] = right[j];
        j++;
        k++;
    )
}

Starting from the main function:

1. The data array data_array is initialized with values (10, 4, 20, 19, 3, 11).
2. The size 6 and merge_sort is called with low 0 and high 5.
3. In the merge_sort function, the array is repeatedly divided into halves until the base condition low < high is met.
4. The merge function sorts and merges the divided arrays.

Each function call and loop iteration is carefully traced, showing the logic of how the array is split, recursively sorted, and then merged.

Keywords

• Recursive Merge Sort
• Trace Code
• Execution Line
• Robo Minions App
• Divide and Conquer
• Algorithm Complexity

FAQ

Q1: What is the purpose of the merge function in merge sort? A1: The merge function combines two sorted sub-arrays into a single sorted array.

Q2: Why do we need to divide the array in merge sort? A2: Dividing the array allows us to break down the problem into smaller, more manageable pieces, which are easier to sort and merge.

Q3: Can the merge sort algorithm handle an array with an odd number of elements? A3: Yes, merge sort can handle arrays with both odd and even numbers of elements. The middle index calculation will naturally handle such cases.

Q4: What is the time complexity of merge sort? A4: The time complexity of merge sort is O(n log n).

Q5: Why is merge sort preferred over other sorting algorithms for large datasets? A5: Merge sort has a consistent O(n log n) time complexity and is stable, making it suitable for large datasets that require guaranteed and efficient sorting.

That’s it for the detailed walkthrough of merge sort using recursion. Don’t forget to download the Robo Minions app for more code-tracing and interview preparation tips. Thank you for watching and happy coding!