{"id":791,"date":"2025-11-21T08:53:21","date_gmt":"2025-11-21T03:23:21","guid":{"rendered":"https:\/\/codexplained.in\/?p=791"},"modified":"2025-11-21T08:53:21","modified_gmt":"2025-11-21T03:23:21","slug":"merge-sort-using-by-looping","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=791","title":{"rendered":"Merge Sort Using by looping"},"content":{"rendered":"
\n#include <stdio.h>\n\n\/\/ Function to merge two subarrays into a single sorted array\nvoid merge(int arr[], int left, int mid, int right) \n{\n    int i, j, k;\n    int n1 = mid - left + 1; \/\/ Size of the first subarray\n    int n2 = right - mid;    \/\/ Size of the second subarray\n\n    \/\/ Temporary arrays to hold the two subarrays\n    int L[n1], R[n2];\n\n    \/\/ Copy data to temporary arrays L[] and R[]\n    for (i = 0; i < n1; i++)\n        L[i] = arr[left + i];\n    for (j = 0; j < n2; j++)\n        R[j] = arr[mid + 1 + j];\n\n    \/\/ Merge the temporary arrays back into arr[left..right]\n    i = 0; \/\/ Initial index of first subarray\n    j = 0; \/\/ Initial index of second subarray\n    k = left; \/\/ Initial index of merged subarray\n    while (i < n1 && j < n2) \n{\n        if (L[i] <= R[j]) \n{\n            arr[k] = L[i];\n            i++;\n        } \nelse \n{\n            arr[k] = R[j];\n            j++;\n        }\n        k++;\n    }\n\n    \/\/ Copy the remaining elements of L[], if any\n    while (i < n1) \n{\n        arr[k] = L[i];\n        i++;\n        k++;\n    }\n\n    \/\/ Copy the remaining elements of R[], if any\n    while (j < n2) \n{\n        arr[k] = R[j];\n        j++;\n        k++;\n    }\n}\n\n\/\/ Function to implement Merge Sort using recursion\nvoid mergeSort(int arr[], int left, int right) \n{\n    if (left < right) \n{\n        \/\/ Find the middle point to divide the array into two halves\n        int mid = left + (right - left) \/ 2;\n\n        \/\/ Call mergeSort on the first half\n        mergeSort(arr, left, mid);\n\n        \/\/ Call mergeSort on the second half\n        mergeSort(arr, mid + 1, right);\n\n        \/\/ Merge the two halves sorted in the previous steps\n        merge(arr, left, mid, right);\n    }\n}\n\n\/\/ Function to print an array\nvoid printArray(int arr[], int size) \n{\n    int i;\n    for (i = 0; i < size; i++)\n        printf("%d ", arr[i]);\n    printf("\\n");\n}\n\nint main() \n{\n    int arr[] = {12, 11, 13, 5, 6, 7};\n    int arr_size = sizeof(arr) \/ sizeof(arr[0]);\n\n    printf("Given array is: \\n");\n    printArray(arr, arr_size);\n\n    mergeSort(arr, 0, arr_size - 1);\n\n    printf("\\nSorted array is: \\n");\n    printArray(arr, arr_size);\n    return 0;\n}\n<\/pre><\/div>\n\n\n
Explanation:<\/strong>–<\/p>\n\n\n\n
    \n
  1. Merge Sort Overview<\/strong>: Merge Sort is a divide-and-conquer<\/strong> algorithm that works by recursively dividing the array into smaller subarrays and then merging them back in sorted order. The key steps are:<\/li>\n<\/ol>\n\n\n\n
      \n
    • Divide the array into two halves.<\/li>\n\n\n\n
    • Recursively apply merge sort to both halves.<\/li>\n\n\n\n
    • Merge the two sorted halves back into a single sorted array.<\/li>\n<\/ul>\n\n\n\n
      <\/p>\n\n\n\n
      2<\/strong>. mergeSort()<\/code> Function<\/strong>:<\/p>\n\n\n\n
        \n
      • Base Case<\/strong>: If the array has one or no elements (i.e., left >= right<\/code>), then the array is already sorted.<\/li>\n\n\n\n
      • Recursive Case<\/strong>: The array is split into two halves, and mergeSort()<\/code> is called recursively on each half.<\/li>\n\n\n\n
      • After sorting both halves, the merge()<\/code> function is used to merge the sorted halves back together.<\/li>\n<\/ul>\n\n\n\n
        3<\/strong>. merge()<\/code> Function<\/strong>:<\/p>\n\n\n\n
          \n
        • This function merges two sorted subarrays into a single sorted array.<\/li>\n\n\n\n
        • The two subarrays are [left..mid]<\/code> and [mid+1..right]<\/code>.<\/li>\n\n\n\n
        • The merging process uses temporary arrays L[]<\/code> and R[]<\/code> to hold the left and right subarrays. The elements from L[]<\/code> and R[]<\/code> are compared, and the smaller element is added back to the original array arr[]<\/code>.<\/li>\n<\/ul>\n\n\n\n
          4<\/strong>. printArray()<\/code> Function<\/strong>:<\/p>\n\n\n\n
            \n
          • This function simply prints the elements of the array.<\/li>\n<\/ul>\n\n\n\n
            5<\/strong>. Main Function<\/strong>:<\/p>\n\n\n\n
              \n
            • An array of integers is initialized, and its size is determined.<\/li>\n\n\n\n
            • The original (unsorted) array is printed.<\/li>\n\n\n\n
            • The mergeSort()<\/code> function is called to sort the array.<\/li>\n\n\n\n
            • Finally, the sorted array is printed.<\/li>\n<\/ul>\n\n\n\n
              Output:-<\/strong><\/p>\n\n\n\n
              When you run this program, you will see the following output:<\/p>\n\n\n
              \nGiven array is: \n12 11 13 5 6 7 \n\nSorted array is: \n5 6 7 11 12 13 \n\n<\/pre><\/div>\n\n\n
              How the Program Works:<\/strong><\/p>\n\n\n\n
                \n
              • Initially, the array [12, 11, 13, 5, 6, 7]<\/code> is divided into two halves:\n
                  \n
                • [12, 11, 13]<\/code><\/li>\n\n\n\n
                • [5, 6, 7]<\/code><\/li>\n<\/ul>\n<\/li>\n\n\n\n
                • Each half is further divided:\n
                    \n
                  • [12, 11, 13]<\/code> becomes [12, 11]<\/code> and [13]<\/code>, and [12, 11]<\/code> becomes [12]<\/code> and [11]<\/code>.<\/li>\n\n\n\n
                  • [5, 6, 7]<\/code> becomes [5, 6]<\/code> and [7]<\/code>, and [5, 6]<\/code> becomes [5]<\/code> and [6]<\/code>.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                  • Once the subarrays contain only one element, they are merged in sorted order:\n
                      \n
                    • [12]<\/code> and [11]<\/code> are merged into [11, 12]<\/code>.<\/li>\n\n\n\n
                    • [5]<\/code> and [6]<\/code> are merged into [5, 6]<\/code>.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                    • This process continues until the entire array is merged back together in sorted order.<\/li>\n<\/ul>\n\n\n\n
                      <\/p>\n