fueanta

Merge Sorting.

Oct 15th, 2016
149
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Assignment Name : Merge Sort [Implementation in C or CPP]
  2. // Time Complexity : O(n log (n))
  3. // *Compiler : "Microsoft Visual Studio"
  4. // AUTHOR : Fueanta
  5. // Date : Oct 15, 2016
  6.  
  7. #include "cstdio"
  8. #define MAX 100
  9.  
  10. void Merge(int *, int, int, int);
  11. void MergeSort(int *, int, int);
  12.  
  13. void main() {
  14.     int arr[MAX]; int size;
  15.     printf("Array size : "); scanf_s("%d", &size);
  16.     printf("\nGive the array elements...\n\n");
  17.     for (int i = 0; i < size; i++) {
  18.         printf("Element %d : ", i + 1);
  19.         scanf_s("%d", &arr[i]);
  20.     }
  21.     printf("\nGiven array without sorting:\n\n");
  22.     for (int i = 0; i < size; i++)
  23.         printf("|%d| ", arr[i]);
  24.     MergeSort(arr, 0, size - 1);
  25.     printf("\n\nGiven array after merge sorting:\n\n");
  26.     for (int i = 0; i < size; i++)
  27.         printf("|%d| ", arr[i]);
  28.     printf("\n\n");
  29. }
  30.  
  31. void MergeSort(int arr[], int first, int last) {
  32.     if (first < last) {
  33.         int MID = (first + last) / 2;
  34.         MergeSort(arr, first, MID);
  35.         MergeSort(arr, MID + 1, last);
  36.         Merge(arr, first, MID, last);
  37.     }
  38. }
  39.  
  40. void Merge(int arr[], int first, int MID, int last) {
  41.     int i1, j1; i1 = j1 = first;
  42.     int i2 = MID + 1, demo[MAX];
  43.     while (i1 <= MID && i2 <= last) {
  44.         if (arr[i1] <= arr[i2])
  45.             demo[j1++] = arr[i1++];
  46.         else demo[j1++] = arr[i2++];
  47.     }
  48.     while (i1 <= MID) demo[j1++] = arr[i1++];
  49.     while (i2 <= last) demo[j1++] = arr[i2++];
  50.     for (int i = first; i <= last; i++) {
  51.         arr[i] = demo[i];
  52.     }
  53. }
RAW Paste Data