#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <sys/resource.h>
#include <stdbool.h>
#include <pthread.h>

#define SIZE 2

struct block {
    int size;
    int *first;
};

// void print_block_data(struct block *blk) {
//     printf("size: %d address: %p\n", blk->size, blk->first);
// }

/* Combine the two halves back together. */
void merge(struct block *left, struct block *right) {
	int combined[left->size + right->size];
	int dest = 0, l = 0, r = 0;
	while (l < left->size && r < right->size) {
		if (left->first[l] < right->first[r])
			combined[dest++] = left->first[l++];
		else
			combined[dest++] = right->first[r++];
	}
	while (l < left->size)
		combined[dest++] = left->first[l++];
	while (r < right->size)
		combined[dest++] = right->first[r++];
    memmove(left->first, combined, (left->size + right->size) * sizeof(int));
}
int count=0;
/* Merge sort the data. */
void *merge_sort(struct block *my_data) {
    int fd[2];
    pid_t ls_pid,sort_pid;
    // print_block_data(my_data);
    if (my_data->size > 1) {
        struct block left_block;
        struct block right_block;
        left_block.size = my_data->size / 2;
        left_block.first = my_data->first;
        right_block.size = left_block.size + (my_data->size % 2);
        right_block.first = my_data->first + left_block.size;
        //create pipe
        if (count == 0 ){
            count++;
            if (pipe(fd) == -1){
                fprintf(stderr,"pipe failed");
                return 1;
            }
            sort_pid = fork();
            if (sort_pid < 0){
                perror("/nChile 2 fork failed");
                return 1;
            }
            if (sort_pid == 0){
                //I AM PARENT
                merge_sort(&left_block);

            }else{
                //I AM CHILd
                merge_sort(&right_block);
                write(fd[0],&left_block,sizeof(struct block));
            }
            read(fd[0],&left_block,sizeof(struct block));
            merge(&left_block, &right_block);
        }

        merge_sort(&right_block);
        merge_sort(&left_block);
        merge(&left_block, &right_block);
        return NULL;
    }
    return NULL;
}

/* Check to see if the data is sorted. */
bool is_sorted(int data[], int size) {
    bool sorted = true;
    for (int i = 0; i < size - 1; i++) {
        if (data[i] > data[i + 1])
            sorted = false;
    }
    return sorted;
}

int main(int argc, char *argv[]) {
    struct rlimit r_limit;
    getrlimit(RLIMIT_STACK, &r_limit);
    r_limit.rlim_cur = 1000000010000;
    setrlimit(RLIMIT_STACK, &r_limit);


	long size;

	if (argc < 2) {
		size = SIZE;
	} else {
		size = atol(argv[1]);
	}
    struct block start_block;
    int data[size];
    start_block.size = size;
    start_block.first = data;
    for (int i = 0; i < size; i++) {
        data[i] = rand();
    }
    printf("starting---\n");
    merge_sort(&start_block);
    printf("---ending\n");
    printf(is_sorted(data, size) ? "sorted\n" : "not sorted\n");
    exit(EXIT_SUCCESS);
}