MERGE-SORT(A, p, r) // A is array of numbers
 {                   // p is starting index of array
                     // r is last index of array
     if p < r
     then q <- ⌊(p + r)⌋ / 2;  
         MERGE-SORT(A, p, q)
         MERGE-SORT(A, q + 1, r)
         MERGE(A, p, q, r)
}

 
 MERGE(A, p, q, r)
 n1 <- q - p + 1
 n2 <- r - q
 create arrays L[1...n1 + 1] and R[1... n2 + 1] // It took O(n) space
 
 //Assign elements to new sub arrays
 for i <- 1 to n1
     do L[i] <- A[p + i - 1]
     
for j <- 1 to n2
    do R[j] <- A[q + j]
    
//Mark end of array
L[n1 + 1] <- ∞
R[n2 + 1] <- ∞

 
 i <- 1
 j <- 1
 
 for k <- p to r {
     do if L[i] <= R[j]
         then A[k] <- L[i]
             i <- i + 1
         else A[k] <- R[j]
            j <- j + 1
}

  
  // Merge Sort example
  // For input array
  // 2 8 7 1 3 5 6 4 9 0
  //
  // First partion in L[] and R[] will be
  // L[] = 2 8 7 1 3 ==> L[] = 2 8 7 | R[] = 1 3 ==> L[] = 2 8 | R[] = 7
  // R[] = 5 6 4 9 0
  //
 #include <stdio.h>
  
 #define EOA 100000  //End of array
  
 // To enable debug messages uncomment #define
 // #define DEBUG 1
  
 #ifdef DEBUG
 #  define D(x) x
 #else
 #  define D(x)
 #endif
  
 void mergesort(int arr[], int p, int r); 
 void merge(int arr[], int p, int q, int r); 
  
 int arr[10] = {2, 8, 7, 1, 3, 5, 6, 4, 9, 0}; 
  
 int main()
 {
     int i = 0;
     printf("Input array\n");
     for (i = 0; i <= 9; i++) {
         printf("%d ", arr[i]);
     }   
     printf("\n\n");
  
     mergesort(arr, 0, 9); 
  
     printf("Sorted output\n");
     for (i = 0; i <= 9; i++) {
         printf("%d ", arr[i]);
     }   
     printf("\n");
  
     return 0;
 }
  
 void mergesort(int arr[], int p, int r)
 {
     if (p < r) {
         int q = (p + r) / 2;
  
         mergesort(arr, p, q);
         mergesort(arr, q+1, r);
         merge(arr, p, q, r);
     }
 }
  
 void merge(int arr[], int p, int q, int r)
 {
     int n1 = q - p + 1;
     int n2 = r - q;
     int i = 0;
     int j = 0;
  
     int L[15];
     int R[15];
  
     //Copy elements from p to n1 in L[]
     for (i = 0; i < n1; i++) {
         L[i] = arr[p + i];
     }
     L[i] = EOA;
  
     for (j = 0; j < n2; j++) {
         R[j] = arr[q + j + 1];
     }
     R[j] = EOA;
  
     int lindx = 0;
     int rindx = 0;
     //Merge array L[] and R[]
     for (i = p; i <= r; i++) {
         if(L[lindx] <= R[rindx]) {
             arr[i] = L[lindx++];
         } else {
             arr[i] = R[rindx++];
         }
     }
  
     // Print debug statements
     D(printf("\n######################\n"));
     D(printf("Left array\n"));
  
     for (i = 0; i < n1; i++) {
         D(printf("%d ", L[i]));
     }
  
     D(printf("\nRight array\n"));
    for (i = 0; i < n2; i++) {
        D(printf("%d ", R[i]));
    }
 
    D(printf("\nAfter Merge\n"));
    for (i = p; i <= r; i++) {
        D(printf("%d ", arr[i]));
    }
    D(printf("\n\n"));
}

 
 // Quick Sort example
 // For input array
 // 2 8 7 1 3 5 6 4
 //
 #include <stdio.h>
 #define IPSIZE 8
  
 // To enable debug messages uncomment #define
// #define DEBUG 1
 
#ifdef DEBUG
#  define D(x) x
#else
#  define D(x)
#endif
 
void quicksort(int arr[], int p, int r); 
int partition(int arr[], int p, int r); 
void swap(int i, int j); 
 
int arr[IPSIZE] = {2, 8, 7, 1, 3, 5, 6, 4}; 
 
int main()
{
    int i = 0;
    printf("Input array\n");
    for (i = 0; i <= IPSIZE - 1; i++) {
        printf("%d ", arr[i]);
    }   
    printf("\n\n");
 
    quicksort(arr, 0, IPSIZE - 1); 
 
    printf("Sorted output\n");
    for (i = 0; i <= IPSIZE - 1; i++) {
        printf("%d ", arr[i]);
    }   
    printf("\n");
 
    return 0;
}
 
void quicksort(int arr[], int p, int r)
{
    if (p < r) {
        int pivotIndx = partition(arr, p, r);
 
        quicksort(arr, p, pivotIndx - 1);
        quicksort(arr, pivotIndx + 1, r);
    }
}
 
int partition(int arr[], int p, int r)
{
    int pivot = arr[r];
    int i = p - 1;
    int j = 0;
 
    // Debug messages
    D(printf("\n############\n"));
    D(printf("Partition\n"));
    D(printf("p=%d, r=%d, pivot=%d\n", p, r, pivot));
    D(printf("Elements\n"));
    for (j = p; j <= r; j++) {
        D(printf("%d ", arr[j]));
    }
    D(printf("\n"));
 
    for (j = p; j <= r - 1; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(i, j);
        }
    }
 
    swap(i + 1, r);
 
    D(printf("Elements after partition\n"));
    for (j = p; j <= r; j++) {
        D(printf("%d ", arr[j]));
    }
    D(printf("\n"));
 
    return (i + 1);
}
 
void swap(int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}