MergeSort.cpp

#include<iostream>
using namespace std;
void merge(int arr[],int s,int e){
    int mid = (s + e)/2;
    int len1 = mid - s + 1;
    int len2 = e - mid;
    int *left = new int[len1]; // Dyanamically creating the left array of size len1
    int *right = new int[len2]; // Dyanamically creating the right array of size len2
    // Copy the values into left array
    int k = s;
    for(int i = 0;i < len1; i++){
        left[i] = arr[k++];
void merge(int arr[], int s, int e) {
    int mid = (s + e) / 2; // Calculate the middle index of the array
    int len1 = mid - s + 1; // Calculate the length of the left subarray
    int len2 = e - mid; // Calculate the length of the right subarray

    int *left = new int[len1]; // Dynamically create the left array of size len1
    int *right = new int[len2]; // Dynamically create the right array of size len2

    int k = s; // Initialize k with the starting index of the original array
    for (int i = 0; i < len1; i++) {
        left[i] = arr[k++]; // Copy elements from the original array to the left array
    }
    // Copy the values into right array
    k = mid + 1;
    for(int i = 0;i < len2; i++){
        right[i] = arr[k++];

    // Copy the values from the original array into the right array
    k = mid + 1; // Start from the index after the middle
    for (int i = 0; i < len2; i++) {
        right[i] = arr[k++]; // Copy elements from the original array to the right array
    }
    // Merge 2 sorted arrays logic
    int leftIndex = 0;
    int rightIndex = 0;
    int mainArrayIndex = s;
    // Run loop until any one array finishes
    while(leftIndex < len1 && rightIndex < len2){
        if(left[leftIndex] < right[rightIndex]){ // Left value is lesser so place that value in mainArray
            arr[mainArrayIndex++] = left[leftIndex++];
        }
        else{ // Right value is lesser
            arr[mainArrayIndex++] = right[rightIndex++];

    int leftIndex = 0; // Initialize an index for the left subarray
    int rightIndex = 0; // Initialize an index for the right subarray
    int mainArrayIndex = s; // Initialize an index for the main (original) array

    // Merge 2 sorted arrays
    while (leftIndex < len1 && rightIndex < len2) {
        if (left[leftIndex] < right[rightIndex]) {
            arr[mainArrayIndex++] = left[leftIndex++]; // Place smaller element in the main array
        } else {
            arr[mainArrayIndex++] = right[rightIndex++]; // Place smaller element in the main array
        }
    }
    // Left array is bigger in size so simply copy these values into main array
    while(leftIndex < len1){

    // Copy any remaining elements from the left subarray into the main array
    while (leftIndex < len1) {
        arr[mainArrayIndex++] = left[leftIndex++];
    }
    // Right array is bigger in size so simply copy these values into main array
    while(rightIndex < len2){

    // Copy any remaining elements from the right subarray into the main array
    while (rightIndex < len2) {
        arr[mainArrayIndex++] = right[rightIndex++];
    }

    // Delete left and right array to save space
}

void mergeSort(int arr[],int s,int e){
    if(s >= e) // Single element remaining or invalid array
        return;