Notes

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>

#define N 100 // Number of integers to sort
#define M 4 // Number of child processes

void generate_numbers(int *numbers, int n) {
for (int i = 0; i < n; i++) {
numbers[i] = rand() % 1000; // Random number between 0 and 999
}
}

void print_numbers(int *numbers, int n) {
for (int i = 0; i < n; i++) {
printf("%d ", numbers[i]);
}
printf("n");
}

void insertion_sort(int *array, int size) {
for (int i = 1; i < size; i++) {
int key = array[i];
int j = i - 1;
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = key;
}
}

void merge(int *array, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;

int *left_array = (int *)malloc(n1 * sizeof(int));
int *right_array = (int *)malloc(n2 * sizeof(int));

for (int i = 0; i < n1; i++) {
left_array[i] = array[left + i];
}
for (int i = 0; i < n2; i++) {
right_array[i] = array[mid + 1 + i];
}

int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (left_array[i] <= right_array[j]) {
array[k] = left_array[i];
i++;
} else {
array[k] = right_array[j];
j++;
}
k++;
}

while (i < n1) {
array[k] = left_array[i];
i++;
k++;
}

while (j < n2) {
array[k] = right_array[j];
j++;
k++;
}

free(left_array);
free(right_array);
}

void merge_sort_sections(int *array, int section_size, int num_sections) {
int *indices = (int *)malloc((num_sections + 1) * sizeof(int));
for (int i = 0; i <= num_sections; i++) {
indices[i] = i * section_size;
}
indices[num_sections] = N; // End of the array

for (int i = 1; i < num_sections; i++) {
merge(array, 0, indices[i] - 1, indices[i + 1] - 1);
}

free(indices);
}

int main() {
int numbers[N];
int portion_size = N / M;
int pipes[M][2];
pid_t pids[M];

generate_numbers(numbers, N);

printf("Unsorted numbers:n");
print_numbers(numbers, N);

// Create pipes
for (int i = 0; i < M; i++) {
if (pipe(pipes[i]) == -1) {
perror("pipe");
exit(EXIT_FAILURE);
}
}

// Create M child processes
for (int i = 0; i < M; i++) {
pids[i] = fork();
if (pids[i] < 0) {
perror("fork");
exit(EXIT_FAILURE);
} else if (pids[i] == 0) { // Child process
close(pipes[i][0]); // Close read end of the pipe

int start = i * portion_size;
int end = (i == M - 1) ? N : (i + 1) * portion_size;
insertion_sort(&numbers[start], end - start);

if (write(pipes[i][1], &numbers[start], (end - start) * sizeof(int)) == -1) {
perror("write");
exit(EXIT_FAILURE);
}

close(pipes[i][1]); // Close write end of the pipe
exit(EXIT_SUCCESS);
} else {
close(pipes[i][1]); // Close write end of the pipe in parent
}
}

// Parent process must wait for all child processes to finish
for (int i = 0; i < M; i++) {
wait(NULL);
}

// Collect sorted portions from child processes
for (int i = 0; i < M; i++) {
int start = i * portion_size;
int end = (i == M - 1) ? N : (i + 1) * portion_size;

if (read(pipes[i][0], &numbers[start], (end - start) * sizeof(int)) == -1) {
perror("read");
exit(EXIT_FAILURE);
}

close(pipes[i][0]); // Close read end of the pipe
}

// Merge the sorted portions
merge_sort_sections(numbers, portion_size, M);

// Print the final sorted array
printf("Sorted numbers:n");
print_numbers(numbers, N);

return 0;
}