insert_merge_sort.c

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>

/* Insertion Sort */
void insertion_sort(long long arr[], int n) {
	int i, j;

	for (i = 1; i < n; i++) {
		j = i;
		while (j > 0 && arr[j-1] > arr[j]) {
			/* Swap */
			arr[j-1] += arr[j];
			arr[j] = arr[j-1] - arr[j];
			arr[j-1] = arr[j-1] - arr[j];

			j--;
		}
	}
}

void merge(long long int arr[],
	   long long int left[], int left_idx,
	   long long int right[], int right_idx) {

	int x = 0, y = 0, z = 0;

	while(x < left_idx && y < right_idx) {
		if(left[x] < right[y]) {
			arr[z] = left[x];
			x++;
			z++;
		}
		else {
			arr[z] = right[y];
			y++;
			z++;
		}
	}
	while(x < left_idx) {
		arr[z] = left[x];
		x++;
		z++;
	}
	while(y < right_idx) {
		arr[z] = right[y];
		y++;
		z++;
	}
}

void merge_sort(long long int arr[], int n) {

	if(n < 2) return;

	int mid = n/2;
	long long int left[mid], right[n - mid];

	for(int i = 0; i < mid; i++)
		left[i] = arr[i];

	for(int i = mid; i < n; i++)
		right[i-mid] = arr[i];

	merge_sort(left, mid);
	merge_sort(right, n-mid);
	merge(arr, left, mid, right, n-mid);
}

void randomize(long long array[], int n) {
	srand(time(NULL));
	if (n > 1) {
		for (int i = 0; i < n - 1; i++) {
			int j = i + rand() / (RAND_MAX / (n - i) + 1);
			long long temp = array[j];
			array[j] = array[i];
			array[i] = temp;
		}
	}
}

int main(void) {
        int n;
        int a;
        int r;

        /* read from user */
        printf("Enter n, a, r:\n");
        scanf("%d", &n);
        scanf("%d", &a);
        scanf("%d", &r);

        long long asc[n];
        long long desc[n];
        long long random[n];

	asc[0] = a;
        for (int i = 1; i < n; i++) {
                a *= r;
                asc[i] = a;
        }

        printf("Ascending:\n");
        for (int i = 0; i < n; i++)
                printf("%lld ", asc[i]);
        printf("\n");

	insertion_sort(asc, n);
	printf("Sorted array using asc array by Insertion sort:\n");
	for (int i = 0; i < n; i++)
		printf("%lld ", asc[i]);
	printf("\n");

	merge_sort(desc, n);
	printf("Sorted array using asc array by Merge sort:\n");
	for (int i = 0; i < n; i++)
		printf("%lld ", asc[i]);
	printf("\n");

	int j;
	for (int i=0, j = n-1; i < n; i++, j--)
		desc[j] = asc[i];
        printf("Descending:\n");
        for (int i = 0; i < n; i++)
                printf("%lld ", desc[i]);
        printf("\n");

	insertion_sort(desc, n);
	printf("Sorted array using desc array by Insertion sort:\n");
	for (int i = 0; i < n; i++)
		printf("%lld ", desc[i]);
	printf("\n");

	merge_sort(desc, n);
	printf("Sorted array using desc array by Merge sort:\n");
	for (int i = 0; i < n; i++)
		printf("%lld ", desc[i]);
	printf("\n");

	randomize(asc, n);
        printf("Random:\n");
        for (int i = 0; i < n; i++)
                printf("%lld ", asc[i]);
        printf("\n");

	insertion_sort(asc, n);
	printf("Sorted array by Insertion sort:\n");
	for (int i = 0; i < n; i++)
		printf("%lld ", asc[i]);
	printf("\n");

	merge_sort(desc, n);
	printf("Sorted array by Merge sort:\n");
	for (int i = 0; i < n; i++)
		printf("%lld ", asc[i]);
	printf("\n");

        return 0;
}