MergeSort (C)

mergeSort.c

#include <stdio.h>

/* Remember not to use ++ or -- with these macros! */
#ifndef max
	#define max( a, b ) ( ((a) > (b)) ? (a) : (b) )
#endif

#ifndef min
	#define min( a, b ) ( ((a) < (b)) ? (a) : (b) )
#endif

#define N 10

void copyArray(int *A, int* B,const int n);
void BottomUpSort(int *A, int* B,const int n);
void BottomUpMerge(int A[], int iLeft, int iRight, int iEnd, int B[]);
void fillArray(int* array, const int n);
void printArray(int* array, const int n);

int main(void)
{
    int test[N], helper[N];
    
    fillArray(test, N);
    printf("Before sorting:\n");
    printArray(test, N);
    
    bottomUpSort(test, helper, N);
    
    printf("After sorting:\n");
    printArray(test, N);
    return 0;
}
/* Copy array B to array A */
void copyArray(int *A, int* B,const int n)
{
    int i;
    for(i = 0 ; i < n ; i++)
        A[i] = B[i];
}

void bottomUpMerge(int A[], int iLeft, int iRight, int iEnd, int B[])
{
  int i0 = iLeft;
  int i1 = iRight;
  int j;
 
  /* While there are elements in the left or right lists */
  for(j = iLeft; j < iEnd; j++)
  {
      /* If left list head exists and is <= existing right list head */
      if (i0 < iRight && (i1 >= iEnd || A[i0] <= A[i1]))
      {
          B[j] = A[i0];
          i0 = i0 + 1;
      }
      else
      {
          B[j] = A[i1];
          i1 = i1 + 1;
      }
  }
}

/* array A[] has the items to sort; array B[] is a work array */
void BottomUpSort(int *A, int* B,const int n)
{
  int width;
 
  /* Each 1-element run in A is already "sorted". */
 
  /* Make successively longer sorted runs of length 2, 4, 8, 16... until whole array is sorted. */
  for(width = 1; width < n; width = 2 * width)
  {
      int i;
 
      /* Array A is full of runs of length width. */
      for(i = 0; i < n; i = i + 2 * width)
      {
          /* Merge two runs: A[i:i+width-1] and A[i+width:i+2*width-1] to B[] */
          /* or copy A[i:n-1] to B[] ( if(i+width >= n) ) */
          bottomUpMerge(A, i, min(i+width, n), min(i+2*width, n), B);
      }
 
      /* Now work array B is full of runs of length 2*width. */
      /* Copy array B to array A for next iteration. */
      /* A more efficient implementation would swap the roles of A and B */
      copyArray(A, B, n);
      /* Now array A is full of runs of length 2*width. */
    }
}

void fillArray(int* array, const int n)
{
    int i;
    for(i = 0 ; i < n ; i++)
        array[i] = n - i;
}
void printArray(int* array, const int n)
{
    int i;
    for(i = 0 ; i < n ; i++)
        printf("array[%d] = %d\n", i, array[i]);
}

This code was developed by me, G. Samaras.

Have questions about this code? Comments? Did you find a bug? Let me know!😀
Page created by G. (George) Samaras (DIT)

2 thoughts on “MergeSort (C)

  1. C:\Users\Josh2\Documents>gcc -std=c99 -Wall -c gsamaras.c
    gsamaras.c: In function ‘main’:
    gsamaras.c:28:5: warning: implicit declaration of function ‘bottomUpSort’ [-Wimp
    licit-function-declaration]
    gsamaras.c: At top level:
    gsamaras.c:66:1: warning: return type defaults to ‘int’ [enabled by default]
    gsamaras.c: In function ‘bottomUpSort’:
    gsamaras.c:91:1: warning: control reaches end of non-void function [-Wreturn-typ
    e]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s