Сортировка слиянием без сбоя массивов

---

Дорогие все,

Мне пришла в голову блестящая идея сделать код сортировки слиянием без рекурсивного создания массивов (очевидно, не связанных списков). Логика кажется правильной, и каждая переменная ведет себя так, как должна, за исключением одной, и я просто не могу понять, почему. Надеюсь, у кого-нибудь найдется время мне помочь.

Я напишу отдельную программу, которая выполняет сортировку слиянием в связанных списках, но здесь я хотел преодолеть главную слабость сортировки слиянием с точки зрения дополнительных накладных расходов, поэтому решил поэкспериментировать с этим.

Пожалуйста, смотрите код ниже:

/* includes and macros */
// required for input / output with minGW GCC
#include <stdio.h>
#define printf __mingw_printf

// required for the dynamic storage allocation and the random integer generator functions
#include <stdlib.h>

// required for the time function, which is required for rand() to work properly
#include <time.h>



/* type definitions  (structs go here) */



/* global declarations */
static unsigned short n = 0;



/* function prototypes */
void swapSort (int *, int *);
void mergeSort (int []);



/* main function */
int main ()
{
	/* some initial declarations & initializations */
	// ask the user for the amount of integers to sort
	printf("How many integers do you want sorted by Merge Sort? ");
	scanf("%hu", &n);

	// for rand()
	srand(time(NULL));

	// array input
	int arrayInput[n];


	/* array input */
	// input taken from the rand() function
	printf ("\n");
	for (register unsigned short i = 0; i <= n-1; i++)
		arrayInput[i] = rand();

	// printing the input so the user knows exactly what rand() produced
	printf ("\n");
	for (register unsigned short i = 0; i <= n-1; i++)
		printf ("[%d] ", arrayInput[i]);
	printf ("\n");


	/* sort the list by Merge Sort */
	mergeSort(arrayInput);


	/* print the sorted array */
	printf("\n");
	for (register unsigned short i = 0; i <= n-1; i++)
		printf("[%d] ", arrayInput[i]);
	printf("\n");


	/* exit main and the program */
	return 0;
}



/* function definitions */
/* simple swapping function */
void swapSort (int *a, int *b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}


/* the Merge Sort function, improving upon bubble sort */
void mergeSort (int mainArray[])
{
	// sort the subarrays formed by every two elements, then by every four elements, then by 8, etc.
	for (unsigned short sizeSubArr = 2; sizeSubArr <= n;)  // set the outer loop so that it sorts all the subarrays of a specific size; the subarray size will change per iteration
									      // of the loop so there may be a remainder subarray of a different size than sizeSubArr
	SubArrayMarkers:
	{
		unsigned short total_number_of_subarrays = n / sizeSubArr;
		unsigned short remSizeSubArr = n % sizeSubArr;
		unsigned short subArrLen = sizeSubArr;
		for (unsigned short mainIndex = 0, subArrNo = 1; subArrNo <= total_number_of_subarrays; mainIndex++)  // a loop that marks the beginning of each subarray as it goes through
																	                   // the main array and then the subarray is sorted by this loop's inner loops
																	                   // it also keeps track of the index of the main array
		{
			BubbleSort:
			for (unsigned short j = 0; j <= n; j = 0)  // this is where bubble sort starts, with the infinite outer loop to be broken if there are no swaps done within the bubble sort
									    // we set l to mainIndex so that if there are multiple iterations of bubble sort, it doesn't screw up mainIndex
			{
				unsigned short l = mainIndex;
				for (register unsigned short k = 1; k <= subArrLen-1; k++, l++)  // one bubble sort iteration through the current sub array of the outer loop
				{
					if (mainArray[l] > mainArray[l+1])
					{
						swapSort(&mainArray[l], &mainArray[l+1]);
						j++;
					}
				}
				if (j == 0)
				{
					mainIndex = l;  // once a subarray is sorted, we need to set mainindex to l's current value so that it can start on the next subarray the next time bubble sort is invoked
					break;
				}
			}
			subArrNo++;  // the incrementation is done here so that a final iteration can be done on the loop based on the following if statement
			if ((subArrNo > total_number_of_subarrays) && (remSizeSubArr >= 2))
			{
				subArrLen = remSizeSubArr;
				mainIndex++;
				goto BubbleSort;
			}
		}
		sizeSubArr *= 2;  // the incrementation is done here so that a final iteration can be done on the loop based on the following if statement
		if (sizeSubArr > n && remSizeSubArr != 0)
		{
			sizeSubArr = n;
			goto SubArrayMarkers;
		}
	}
}

Что я уже пробовал:

Я отлаживал, отлаживал и отлаживал. Я точно определил проблему с переменной l, но не могу понять, почему она раздувается до значения 100+ даже для массива целых чисел 10. В любом случае, он не должен выходить за пределы 10.

---