Linux Calling...: June 2014

Merge sort is one of the efficient sorting algorithms compared to other sorts as Insertion, Selection or Bubble Sort. The algorithm is divide and conquer. We divide the array into 2, sort the 2 arrays and then merge them to form the final result. This is of course a recursive technique. As you can see in the below code, the function merge_sort() is called recursively.
The time complexity is O(nlogn).
In this example, the array is self populated with random values with the help of srand() series of functions after taking the size of the array from the user.

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "time.h"

typedef enum _return_type
{
  ERROR,
  SUCCESS
}return_type_t;

#define NULL_CHECK(x) { if(!x) return ERROR; }

static int merge(int *a1, int n1, int *a2, int n2, int *a)
{

  int i=0, j=0, k=0;

  while(i<n1 && j<n2){
    if(a1[i] <= a2[j]){
      a[k] = a1[i];
      i++;
    }
    else{
      a[k] = a2[j];
      j++;
    }
    k++;
  }

  while(i<n1){
    a[k] = a1[i];
    i++;
    k++;
  }

  while(j<n2){
    a[k] = a2[j];
    j++;
    k++;
  }
  return SUCCESS;
}

static int merge_sort(int *a, int m)
{
  int *a1, *a2;
  int n1, n2;

  if(m<2) return SUCCESS;

  n1 = m >> 1;
  n2 = m - n1;

  a1 = malloc(sizeof(int) * n1);
  NULL_CHECK(a1);
  a2 = malloc(sizeof(int) * n2);
  NULL_CHECK(a2);

  int i=0;
  for(i=0; i<n1; i++)
    a1[i] = a[i];

  for(i=0; i<n2; i++)
    a2[i] = a[i+n1];

  merge_sort(a1, n1);
  merge_sort(a2, n2);

  merge(a1, n1, a2, n2, a);
  free(a1);
  free(a2);

  return 0;

}

static void display(int *a, int n)
{
  int i;
  for(i=0; i<n; i++){
    printf("%d ", a[i]);
  }
  printf("\n");
  return;
}

int main(int argc, char **argv)
{
  int *a;
  int i,n,num;

  scanf("%d", &n);
  a = malloc(sizeof(int) * n);
  NULL_CHECK(a);

  srand ( time(NULL) );

  for(i=0; i<n; i++){
    num = rand() %1000 + 1;
    a[i] = num;
  }

  //display(a, n);
  merge_sort(a, n);
  //display(a, n);

  free(a);
  return 0;
}

Linux Calling...

Tuesday, June 3, 2014

Merge Sort