Thread: sub-arrays for merge Sort

  1. #1
    Registered User
    Join Date
    Oct 2011

    sub-arrays for merge Sort

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

    /* 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");
    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++];
    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 ??

  2. #2
    Registered User
    Join Date
    May 2012
    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.
    I'm the author of MiniBasic: How to write a script interpreter and Basic Algorithms
    Visit my website for lots of associated C programming resources.

  3. #3
    Registered User
    Join Date
    Apr 2013
    Quote Originally Posted by abood1190 View Post
    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.
    Last edited by rcgldr; 05-15-2013 at 04:36 PM.

  4. #4
    TEIAM - problem solved
    Join Date
    Apr 2012
    Melbourne Australia
    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.
    Fact - Beethoven wrote his first symphony in C

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Merge sort fails to sort
    By Cresh07 in forum C++ Programming
    Replies: 3
    Last Post: 09-23-2009, 11:17 AM
  2. Merge sort (sorted arrays)
    By myle in forum C++ Programming
    Replies: 3
    Last Post: 05-09-2007, 02:48 AM
  3. Quick Sort or Merge Sort???
    By swanley007 in forum C++ Programming
    Replies: 6
    Last Post: 11-10-2005, 06:48 PM
  4. Quick sort VS Merge Sort
    By sachitha in forum Tech Board
    Replies: 7
    Last Post: 09-03-2004, 11:57 PM
  5. merge sort and selection sort and time spent on both
    By misswaleleia in forum C Programming
    Replies: 3
    Last Post: 06-04-2003, 02:24 PM