excans:7865bf774d

One possible solution , after reading online descriptions of recursive merge sort, e.g. Dasgupta :

// to compile: gcc -Wall rmergesort.c -lm -o rmergesort

/*
 ============================================================================
 Name        : rmergesort.c
 Author      : Anon
 Version     : 0.1
 Copyright   : (C)2013 under CC-By-SA 3.0 License
 Description : Recursive Merge Sort, Ansi-style
 ============================================================================
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//const int MAX = 200;
const int MAX = 20000000;

int *b;

int printOff = 0;

// this debugging print out of the array helps to show
// what is going on.
void printArray(char* label, int* a, int sz) {
	int h = sz/ 2;
	int i;

	if (printOff) return;

	printf("\n%s:\n", label);

	for (i = 0; i < h; ++i ) {

		printf("%d%c", a[i],
					// add in a newline every 20 numbers
					( ( i != 0 && i % 20 == 0 )? '\n': ' ' ) );
	}

	printf(" | ");
	for (;i < sz; ++i) {
		printf("%d%c", a[i],
					( ( i != 0 && i % 20 == 0 )? '\n': ' ' ) );
	}

	putchar('\n');


}

void mergesort(int* a, int m ) {

	printArray("BEFORE", a, m);

	if (m > 2) {
		// if greater than 2 elements, then recursive
		mergesort(a, m / 2);
		mergesort(a + m / 2, m - m / 2);


	} else if (m == 2 && a[0] > a[1]) {
		// if exactly 2 elements and need swapping, swap
		int t = a[1];
		a[1] = a[0];
		a[0] = t;
		goto end;

	}

	// 1 or greater than 2 elements which have been recursively sorted

	// divide the array into a left and right array
	// merge into the array b with index l.

	int n = m/2;
	int o = m - n;

	int i = 0, j = n;
	int l = 0;
	// i is left, j is right ;
	// l should equal m the size of the array
	while (i < n) {
		if ( j >= m) {
			// the right array has finished, so copy the remaining left array
			for(; i < n; ++i) {
				b[l++] = a[i];
			}

		// the merge operation is to copy the smaller current element and
		// increment the index of the parent sub-array.
		} else if(  a[i] < a[j] ) {
			b[l++] = a[i++];
		} else {
			b[l++] = a[j++];
		}
	}

	while ( j < m) {
		// copy the remaining right array , if any
		b[l++] = a[j++];
	}

	memcpy(a, b, sizeof(int) * l );

end:
	printArray("AFTER", a, m);

	return;

}

void rand_init(int* a, int n) {
	int i;
	for (i = 0; i < n; ++i ) {

		a[i] = rand() % MAX;

	}
}

int main(void) {
	puts("!!!Hello World!!!"); /* prints !!!Hello World!!! */

//	int N = 20;
//    int N = 1000;
//    int N = 1000000;
	int N = 100000000;  // still can't make a stack overflow on ubuntu,4GB, phenom
	printOff = 1;

	int *a;

	b = calloc( N, sizeof(int));

	a = calloc( N, sizeof(int));

	rand_init(a, N);

	mergesort(a, N);

	printOff = 0;

	printArray("LAST", a, N);

	free(a);
	free(b);

	return EXIT_SUCCESS;
}


/* Having failed to translate my concept of non-recursive merge sort,
 * I tackled the easier case of recursive merge sort.
 * The next task is to translate the recursive version to a non-recursive
 * version. This could be done by replacing calls to mergesort, with
 * pushes onto a stack of
 * tuples of ( <array start address>, <number of elements to process> )
 */

/* The central idea of merging, is that two sorted lists can be
 * merged into one sorted list, by comparing the top of each list and
 * moving the lowest valued element onto the end of the new list.
 *  The other list which has the higher valued element keeps its top
 *  element unchanged. When a list is exhausted, copy the remaining other list
 *  onto the end of the new list.
 */

/* The recursive part, is to defer any work in sorting an unsorted list,
 * by dividing it into two lists until there is only 1 or two elements,
 * and if there are two elements, sort them directly by swapping if
 * the first element is larger than the second element.
 *
 * After returning from a recursive call, merge the lists, which will
 * begin with one or two element sorted lists. The result is a sorted list
 * which will be returned to the parent of the recursive call, and can
 * be used for merging.
 */

/* The following is an imaginary discussion about what a programmer
 * might be thinking about when programming:
 *
 * Visualising recursion in terms of a Z80 assembly language, which
 * is similar to most assembly languages, there is a data stack (DS) and
 * a call stack (CS) pointer, and each recursive call to mergesort
 * pushes the return address , which is the program address of the instruction
 * after the call , onto the stack pointed to by CS and CS is incremented,
 * and the address of the array start and integer which is the subarray length
 * onto the data stack pointed to by DS, which will be incremented twice.
 *
 * If the number of recursive , active calls exceed the allowable space for either the call stack
 * or the data stack, then the program will crash , or a process space protection
 * violation interrupt signal will be sent by the CPU, and the interrupt vector
 * for that signal will jump the processor's current instruction pointer to the
 * interrupt handling routine.
 */

References

Wikibooks contributors. "C Programming/Exercise solutions". Wikibooks. Wikibooks. Retrieved 13 May 2024.