Start New Discussion within our Software Development Community

Hi,

I have to do a recursive merge sort here. I got the merge sort done (thanks internet...because my book was useless), but I have to print the sublists as output. Here's the instructions:

"The program must first display the list to be sorted. Then it must display the sublists into which the original list is split during the recursive merge sort process. The program must also display the lists into which the sublists are subsequently merged to form the final sorted list."

I am a little confused imagining this here. Where would I put a print list function into the merge sort?

Here is the merge sort if it helps:

void mergeSort(int a[], int low, int high)
{
	int mid;
	if(low < high)
	{
		mid = (low + high) / 2;
		mergeSort(a, low, mid);
		mergeSort(a, mid + 1, high);
		merge(a, low, high, mid);
	}
}
void merge(int a[], int low, int high, int mid)
{
	int i, j, k, c[50];

	i = low;
	j = mid + 1;
	k = low;
	while((i <= mid)&&(j <= high))
	{
		if(a[i]<a[j])
		{
			c[k] = a[i];
			k++;
			i++;
		}
		else
		{
			c[k] = a[j];
			k++;
			j++;
		}
	}
	while(i <= mid)
	{
		c[k] = a[i];
		k++;
		i++;
	}
	while(j <=  high)
	{
		c[k] = a[j];
		k++;
		j++;
	}
	for(i = low;i < k; i++)
	{
		a[i] = c[i];
	}
}

With a merge sort, you split the original list into smaller lists until they're all individual element lists and then you put them back together in a sorted manner.

You can see this visually on wikipedia:
http://en.wikipedia.org/wiki/File:Merge_sort_algorithm_diagram.svg

You want to print each of those lists shown.

I believe you want to print the lists that you are "passing" here:

mergeSort(a, low, mid);
mergeSort(a, mid + 1, high);

I say "passing" in quotes because you always pass the same array -- variable a -- but you're effectively passing a certain segment of it by defining which part of the array you are talking about with the second and third parameter.

Hope that helps.

This article has been dead for over six months. Start a new discussion instead.