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

Question :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++]; }

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 ??