Advertisement
triclops200

C-merge-sort

Jul 9th, 2013
245
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.19 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. int a[200000] = {0};
  5. #define SIZE sizeof(a)/sizeof(int)
  6. int* merge_sort(int* a,int length)
  7. {
  8.     int* buff = (int*)malloc(sizeof(int)*length);
  9.     int* array = (int*)malloc(sizeof(int)*length);
  10.     memcpy(array,a,length*sizeof(int));
  11.     int i;
  12.     if(length == 1)
  13.     {
  14.         free(buff);
  15.         return array;
  16.     }
  17.     int* tmp;
  18.     int size = 1;
  19.     while(size < length)
  20.     {
  21.         int s;
  22.         int i;
  23.         int j;
  24.         for(s = 0; s <= length/size+1; s += size*2)
  25.         {
  26.             i = s;
  27.             j = s + size;
  28.             int o = s;
  29.             while(!((i >= s + size) &&
  30.                         ((j >= s + size*2) || j >= length)
  31.                    ))
  32.             {
  33.                 if(j >= s + size*2 || j >= length)
  34.                     buff[o++] = array[i++];
  35.                 else if (i >= s + size)
  36.                     buff[o++] = array[j++];
  37.                 else if (array[i] > array[j])
  38.                     buff[o++] = array[j++];
  39.                 else
  40.                     buff[o++] = array[i++];
  41.             }
  42.         }
  43.         tmp = buff;
  44.         buff = array;
  45.         array = tmp;
  46.         size *= 2;
  47.     }
  48.     free(buff);
  49.     return array;
  50. }
  51. int main()
  52. {
  53.     int i;
  54.     //  for(i= 0; i < SIZE; i ++)
  55.     //      printf("%d ",a[i]);
  56.     //  printf("\n");
  57.     int* sorted = merge_sort(a,SIZE);
  58.     //  for(i= 0; i < SIZE; i ++)
  59.     //      printf("%d ",sorted[i]);
  60.     //  printf("\n");
  61.     free(sorted);
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement