Example: Merge Sort without user-defined functions in C in C

// Merge Sort without user-defined functions in C
#include <stdio.h>
#include <stdlib.h> // For malloc (though we'll use a fixed-size array for simplicity here)

int main() {
    // Step 1: Define the array to be sorted and its size
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    // Step 2: Declare a temporary array for merging
    // In a real-world scenario, dynamic allocation (malloc) is preferred for temp_arr
    // For simplicity and to avoid malloc/free complexity within this specific constraint,
    // we use a fixed-size array. Make sure it's large enough.
    int temp_arr[n]; // C99 VLA feature, or declare a large enough fixed size like temp_arr[100]

    // Step 3: Implement the iterative merge sort logic
    // current_size goes from 1 to n/2, doubling in each iteration
    int current_size; 
    // left_start is the starting index of the left sub-array
    int left_start;    

    // Iterate over sub-array sizes (1, 2, 4, ...)
    for (current_size = 1; current_size <= n - 1; current_size = 2 * current_size) {
        // Pick starting point of different sub-arrays of current_size
        for (left_start = 0; left_start < n - 1; left_start += 2 * current_size) {
            // Find ending point of left sub-array. mid is (left_start + current_size - 1)
            int mid = left_start + current_size - 1;

            // Find ending point of right sub-array.
            // right_end is (left_start + 2*current_size - 1)
            int right_end = left_start + 2 * current_size - 1;

            // Adjust mid and right_end to be within array bounds
            if (mid >= n) { // If left sub-array extends beyond array, adjust mid
                mid = n - 1;
            }
            if (right_end >= n) { // If right sub-array extends beyond array, adjust right_end
                right_end = n - 1;
            }

            // Perform the merge operation
            // left_start to mid is left sub-array
            // mid+1 to right_end is right sub-array
            int i, j, k;
            i = left_start;      // Index for the left sub-array
            j = mid + 1;         // Index for the right sub-array
            k = left_start;      // Index for the temporary array

            // Merge the two sub-arrays into temp_arr
            while (i <= mid && j <= right_end) {
                if (arr[i] <= arr[j]) {
                    temp_arr[k++] = arr[i++];
                } else {
                    temp_arr[k++] = arr[j++];
                }
            }

            // Copy the remaining elements of left sub-array, if any
            while (i <= mid) {
                temp_arr[k++] = arr[i++];
            }

            // Copy the remaining elements of right sub-array, if any
            while (j <= right_end) {
                temp_arr[k++] = arr[j++];
            }

            // Copy the merged elements back to the original array
            for (i = left_start; i <= right_end; i++) {
                arr[i] = temp_arr[i];
            }
        }
    }

    // Step 4: Print the sorted array
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}