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

public class MergeSort
{

public static void mergeSort(double[] a, int length)
   {  
     Sort(a, 0, a.length - 1);
   }
public static void Sort(double[] a, int left, int right)
   {  
     if (left < right)
     {
      int mid = (left + right) / 2;
       // sort the first and the second half
      Sort(a, left, mid);
      Sort(a, mid + 1, right);
      merge(a, left, mid, right);
     }
   }
   public static void merge(double[] a, int left, int mid, int right)
   {  

      double[] b = new double[right - left + 1]; // merge both halves into a temporary array b

      int index1 = left;         // next element to consider in the first range
      int index2 = mid + 1;
      int last = right;
      int index = 0;             // next open position in b

      // as long as neither i1 nor i2 past the end, move the smaller into b
      while(index1 <= mid && index2 <= last)
      {  
        if(a[index1] < a[index2])
         {  
          b[index] = a[index1];
            index1++;
         }
         else
         { 
           b[index] = a[index2];
            index2++;
         }
         index++;
      }

      // note that only one of the two while loops
      // below is executed

      // copy any remaining entries of the first half
      while (index1 <= mid)
      { 
        b[index] = a[index1];
         index1++;
         index++;
      }

      // copy any remaining entries of the second half
      while (index2 <= last)
      {  
        b[index] = a[index2];
         index2++;
         index++;
      }
      int s = 0;
      // copy back from the temporary array
      for(int i = left; i <= right; i++)
      {
         a[i] = b[s];
         s++;
      }
   }

public static void main(String[] args)throws FileNotFoundException
{
  Scanner input = new Scanner(new FileReader("input.txt"));
  
  int count = 0;
  int numOfElements = 0;  
  double[] array = new double[10];


  while(input.hasNextDouble())
  {
    array[count] = input.nextDouble();
    count++;
  }
        System.out.println("Unsorted Array");
    for(int i = 0; i < count; i++)
    {
       System.out.print(array[i] + " ");
  }
    System.out.println();
    mergeSort(array, array.length);
    System.out.println("Sorted Array");
    for(int i = 0; i < count; i++)
    {
      System.out.print(array[i] + " ");
    }

input.close();
 }
}

function mergesort(m)
   var list left, right, result
   if length(m) ≤ 1
       return m
   else
       var middle = length(m) / 2
       for each x in m up to middle - 1
           add x to left
       for each x in m at and after middle
           add x to right
       left = mergesort(left)
       right = mergesort(right)
       if last(left) ≤ first(right) 
          append right to left
          return left
       result = merge(left, right)
       return result

function merge(left,right)
   var list result
   while length(left) > 0 and length(right) > 0
       if first(left) ≤ first(right)
           append first(left) to result
           left = rest(left)
       else
           append first(right) to result
           right = rest(right)
   if length(left) > 0 
       append rest(left) to result
   if length(right) > 0 
       append rest(right) to result
   return result