merge sort

program:-

#include<stdlib.h> #include<stdio.h> void merge(int arr[], int l, int m, int r) {     int i, j, k;     int n1 = m - l + 1;     int n2 =  r - m;          int L[n1], R[n2];          for (i = 0; i < n1; i++)         L[i] = arr[l + i];     for (j = 0; j < n2; j++)         R[j] = arr[m + 1+ j];          i = 0;     j = 0;     k = l;     while (i < n1 && j < n2)     {         if (L[i] <= R[j])         {             arr[k] = L[i];             i++;         }         else         {             arr[k] = R[j];             j++;         }         k++;     }          while (i < n1)     {         arr[k] = L[i];         i++;         k++;     }         while (j < n2)     {         arr[k] = R[j];         j++;         k++;     } } void mergeSort(int arr[], int l, int r) {     if (l < r)     {                 int m = l+(r-l)/2;                 mergeSort(arr, l, m);         mergeSort(arr, m+1, r);         merge(arr, l, m, r);     } } void printArray(int A[], int size) {     int i;     for (i=0; i < size; i++)         printf("%d ", A[i]);     printf("\n"); } /* Driver program */ int main() {     int arr[] = {12, 11, 13, 5, 6, 7};     int arr_size = sizeof(arr)/sizeof(arr[0]);     printf("Given array is \n");     printArray(arr, arr_size);     mergeSort(arr, 0, arr_size - 1);     printf("\nSorted array is \n");     printArray(arr, arr_size);     return 0; }

For example, with the Merge Sort algorithm, they define the Merge Function (which I think I have translated correctly) and the recursive MergeSort function (where direct translation to R does not work).

The merge function in pseudo-code is as follows where: A is an array and p, q, and r are indices into the array such that p < q < r. The procedure assumes that the subarrays A[p:q] and A[q+1:r] are in sorted order. It merges them to form a single sorted subarray that replaces the current subarray A[p:r]

Merge(A, p, q, r)
n1 = q - p + 1
n2 = r - q
let L[1...n1+1] and R[1...n2+1] be new arrays
for i = 1 to n1
    L[i] = A[p+i-1]
for j = 1 to n2
    R[j] = A[q+j]
L[n1+1] = infinite
R[n2+1] = infinite
i=1
j=1
for k = p to r
    if L[i] <= R[j]
        A[j] = L[i]
        i = i + 1
    else
        A[k] = R[j]
        j = j + 1

Which I've translated to R as:

Merge <- function(a, p, q, r){
  n1 <- q - p + 1
  n2 <- r - q
  L <- numeric(n1+1)
  R <- numeric(n2+1)
  for(i in 1:n1){
    L[i] <- a[p+i-1]
  }
  for(j in 1:n2){
    R[j] <- a[q+j]
  }
  L[n1+1] <- Inf
  R[n2+1] <- Inf
  i=1
  j=1
  for(k in p:r){
    if(L[i] <= R[j]){
      a[k] <- L[i]
      i <- i +1
    }else{
      a[k] <- R[j]
      j <- j+1
    }
  }
  a
}

And it seems to work fine.

Merge(c(1,3,5, 2,4,6), 1, 3, 6)
[1] 1 2 3 4 5 6

Now the MergeSort function is defined in pseudo-code as follows:

MergeSort(A, p, r)
if p < r
   q = (p+r)/2
   MergeSort(A, p, q)
   MergeSort(A, q+1, r)
   Merge(A, p, q, r)

This assumes that A is passed by reference and that every change is visible to every recursive call, which is not true in R.

So, given the Merge function defined above, how you would implement the MergeSort function in R to obtain the correct results? (if possible, and preferable, but not necessary, somewhat similar to the pseudo-code)