sub-arrays for merge Sort

**abood1190** · 05-15-2013

There is a question in my lab i couldnt figure it out .. I need your help to give me hints not to solve it.

Code:

/* Mergesort: Use merge() to sort an array of size n */
#include <stdio.h>
#include <stdlib.h>
void mergesort(int key[], int n)
{
int j, k, m, *w;
for (m = 1; m < n; m *= 2)
;
if (m != n) {
printf("ERROR: Size of the array is not a power of 2 - bye!\n");
exit(1);
}
w = calloc(n, sizeof(int)); /* allocate workspace */
for (k = 1; k < n; k *= 2) {
for (j = 0; j < n - k; j += 2 * k)
merge(key + j, key + j + k, w + j, k, k); /* merge into w */
for (j = 0; j < n; ++j)
key[j] = w[j]; /* write w back into key */
}
free(w); /* free the workspace */
}

/* Merge a[] of size m and b[] of size n into c[].*/
void merge(int a[], int b[], int c[], int m, int n)
{
int i = 0, j = 0, k = 0;
while (i < m && j < n)
if (a[i] < b[j])
c[k++] = a[i++];
else
c[k++] = b[j++];
while (i < m) /* pick up any remainder */
c[k++] = a[i++];
while (j < n)
c[k++] = b[j++];
}

Question :
Modify mergesort() so that it can be used with an array of any size, not just with a size that is a power of two. Recall that any positive integer can be expressed as a sum of powers of two. For example,
27 = 16 + 8 + 2 + 1
Consider the array as a collection of subarrays of sizes that are powers of two. Sort the subarrays and then use merge() to produce the final sorted array.

==================================================

I tried so many algorithms and all failed!!

What i dont know is how to create subarrays ?? what is the idea ??

**Malcolm McLean** · 05-15-2013

You are passed n, which is a binary number giving the number of elements in the array.
Let's say n is five. The bit for 1 is set, the bit for 2 is clear, the bit for 4 is set, and all other bits are clear. By simply looking at the bits, you have the powers of two that make up that number.

So step one is to break the arrays into chunks of a power of two, and call your power of two algorithm to sort them.

The nest step is to work out how to join up the fragments. Note this step doesn't have to be especially efficient. Assuming 32 bit ints, you can never have more than 32 chunks. Assuming you use all the memory in the world to store your array, you probably won't go above sixty or so chunks.

**rcgldr** · 05-15-2013

Originally Posted by abood1190

What i dont know is how to create subarrays ??

You're already creating sub-arrays with those two nested for loops and the call to merge().

You don't have to change much in order to handle an array of any size, as opposed to a power of 2. The hint about any number being equal to the sum of powers of two doesn't seem helpful, and you don't need to use that bit of information.

Instead you need to adjust the code near the merge() statement to avoid accessing data beyond the end of the array, specifically you need to check the indexes and the size values that you pass to merge() to make sure that no index + size >= n.

**Click_here** · 05-15-2013

You really need to fix your indentation

Most modern IDE's have an auto format option.

Indent style - Wikipedia, the free encyclopedia

I prefer Allman, but they are all as good as each other.

Thread: sub-arrays for merge Sort

Thread Tools

Search Thread

Display

sub-arrays for merge Sort

Similar Threads

Merge sort fails to sort

Merge sort (sorted arrays)

Quick Sort or Merge Sort???

Quick sort VS Merge Sort

merge sort and selection sort and time spent on both