node *findMid(node *head) {
  node *slow = head;
  node *fast = head->next;
  while (fast != NULL && fast->next != NULL) {
    slow = slow->next;
    fast = fast->next->next;
  }
  return slow;
}

node *merge(node *left, node *right) {
  if (left == NULL) {
    return right;
  }
  if (right == NULL) {
    return left;
  }
  node *ans = new node(-1);
  node *temp = ans;
  while (left != NULL && right != NULL) {
    if (left->data < right->data) {
      temp->next = left;
      temp = left;
      left = left->next;
    } else {
      temp->next = right;
      temp = right;
      right = right->next;
    }
  }
  while (left != NULL) {
    temp->next = left;
    temp = left;
    left = left->next;
  }
  while (right != NULL) {
    temp->next = right;
    temp = right;
    right = right->next;
  }
  ans = ans->next;
  return ans;
}

node *mergeSort(node *head) {
  // base case
  if (head == NULL || head->next == NULL) {
    return head;
  }
  // breaking the linked list into two halves
  node *mid = findMid(head);
  node *first = head;
  node *second = mid->next;
  mid->next = NULL;
  // recursive call
  first = mergeSort(first);
  second = mergeSort(second);
  // merging the two sorted halves
  node *result = merge(first, second);
  return result;
}

void merge(int *arr, int s, int e) {
  int mid = s + (e - s) / 2;
  int len1 = mid - s + 1;
  int len2 = e - mid;
  int *first = new int[len1];
  int *second = new int[len2];

  // copy vales
  int mainArrayIndex = s;
  for (int i = 0; i < len1; i++) {
    first[i] = arr[mainArrayIndex++];
  }
  mainArrayIndex = mid + 1;
  for (int i = 0; i < len2; i++) {
    second[i] = arr[mainArrayIndex++];
  }

  // merge 2 sorted arrays
  int index1 = 0;
  int index2 = 0;
  mainArrayIndex = s;
  while (index1 < len1 && index2 < len2) {
    if (first[index1] < second[index2]) {
      arr[mainArrayIndex++] = first[index1++];
    } else {
      arr[mainArrayIndex++] = second[index2++];
    }
  }
  while (index1 < len1) {
    arr[mainArrayIndex++] = first[index1++];
  }
  while (index2 < len2) {
    arr[mainArrayIndex++] = second[index2++];
  }
}

void mergeSort(int *arr, int s, int e) {
  if (s >= e) {
    return;
  }
  int mid = s + (e - s) / 2;
  // left  part
  mergeSort(arr, s, mid);
  // right part
  mergeSort(arr, mid + 1, e);
  // merge
  merge(arr, s, e);
}

import java.util.*;
import java.io.*;

class Solution
{
    public static void main (String[] args) 
    {
        int a[] = new int[]{10,5,30,15,7};
	    int l=0,r=4;
        
        mergeSort(a,l,r);
    	for(int x: a)
	        System.out.print(x+" ");    // OUTPUT : 5 7 10 15 30 
        
    }
    
    static void merge(int arr[], int l, int m, int h){
    
        int n1=m-l+1, n2=h-m;
        int[] left=new int[n1];
        int[]right=new int[n2];
        
        for(int i=0;i<n1;i++)
            left[i]=arr[i+l];
        for(int j=0;j<n2;j++)
            right[j]=arr[m+1+j];
            
        int i=0,j=0,k=l;
        while(i<n1 && j<n2){
            if(left[i]<=right[j])
                arr[k++]=left[i++];
            else
                arr[k++]=right[j++];
        }
        while(i<n1)
            arr[k++]=left[i++];
        while(j<n2)
            arr[k++]=right[j++];    
    }
    
    static void mergeSort(int arr[],int l,int r){
        if(r>l){
            int m=l+(r-l)/2;
            mergeSort(arr,l,m);
            mergeSort(arr,m+1,r);
            merge(arr,l,m,r);
        }
    }
}