Merge Sort Core Implementation (Function Only)
Merge Sort is a classic sorting algorithm based on the Divide and Conquer paradigm.
It works by recursively dividing the array into two halves until each sub-array contains only one element, and then merging the sorted sub-arrays back together.
In this problem, the system's hidden grader will handle all I/O operations (reading inputs and printing outputs) and has already implemented the merge() function for you.
Your task is to implement ONLY the sortSubArray function.
You need to write the recursive logic to divide the array and call the provided merge function to combine the results.
The Provided merge Function
The system provides the following helper function which you can call directly in your code. It merges two already sorted sub-arrays array[low...middle1] and array[middle2...high] into a single sorted segment.
void merge(int array[], size_t low, size_t middle1, size_t middle2, size_t high);
What You Need to Submit
Please submit only the required function implementation (and necessary #include headers). Do NOT include a main() function, otherwise you will receive a Compilation Error.
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
// Declaration of the merge function
void merge(int array[], size_t low, size_t middle1, size_t middle2, size_t high);
// ==========================================
// YOUR TASK: Complete this function
// ==========================================
void sortSubArray(int array[], size_t low, size_t high) {
if ((high - low) >= 1) {
size_t middle1 = (low + high) / 2;
size_t middle2 = middle1 + 1;
// TODO: Fill in the missing core logic here
}
}
// ==========================================
// System logic below. DO NOT MODIFY.
// ==========================================
void merge(int array[], size_t low, size_t middle1, size_t middle2, size_t high) {
size_t left_size = middle1 - low + 1;
size_t right_size = high - middle2 + 1;
int *left_arr = (int*)malloc(left_size * sizeof(int));
int *right_arr = (int*)malloc(right_size * sizeof(int));
for (size_t i = 0; i < left_size; i++) left_arr[i] = array[low + i];
for (size_t i = 0; i < right_size; i++) right_arr[i] = array[middle2 + i];
size_t i = 0, j = 0, k = low;
while (i < left_size && j < right_size) {
if (left_arr[i] <= right_arr[j]) {
array[k++] = left_arr[i++];
} else {
array[k++] = right_arr[j++];
}
}
while (i < left_size) array[k++] = left_arr[i++];
while (j < right_size) array[k++] = right_arr[j++];
free(left_arr);
free(right_arr);
}
int main() {
size_t length;
if (scanf("%zu", &length) != 1) return 0;
int *array = (int*)malloc(length * sizeof(int));
for (size_t i = 0; i < length; i++) {
scanf("%d", &array[i]);
}
if (length > 0) {
sortSubArray(array, 0, length - 1);
}
for (size_t i = 0; i < length; i++) {
printf("%d", array[i]);
if (i < length - 1) printf(" ");
}
printf("\n");
free(array);
return 0;
}
Input Specification
(Handled by the hidden grader)
The first line contains an integer N, representing the length of the array.The second line contains N space-separated integers, representing the elements of the array.1 ≤ N ≤ 10⁵ -2³¹ ≤ array[i] ≤ 2³¹-1
Output Specification
(Handled by the hidden grader)The system will print the sorted array in ascending order, with elements separated by a single space.
Sample Input
10
79 86 60 79 76 71 44 88 58 23Sample Output
23 44 58 60 71 76 79 79 86 88
評論