/************************************************
Grundlegende Algorithmen mit Java,
http://algorithmen-und-problemloesungen.de/
Copyright @2007-2009 by Doina Logofatu

in C#: Michael Gärtner
************************************************/

using System;
using System.Collections.Generic;
using System.IO;

namespace Logofatu
{
    class P05MergeSort
    {
        private static String FileInputName = "MSort.in";
        private static String FileOutputName = "MSort.out";

        private static void mergeSort(int[] arr)
        {
            if ( arr.Length <= 1 )
                return;
            int[] v1 = new int[arr.Length / 2];
            int[] v2 = new int[arr.Length - v1.Length];

            Array.Copy(arr, 0, v1, 0, arr.Length / 2);
            Array.Copy(arr, arr.Length / 2, v2, 0, arr.Length - v1.Length);

            mergeSort(v1);
            mergeSort(v2);

            int i1 = 0, i2 = 0;
            for ( int k = 0; k < v1.Length + v2.Length; )
            {
                if ( (i2 >= v2.Length) || (i1 < v1.Length && v1[i1] <= v2[i2]) )
                {
                    arr[k++] = v1[i1++];
                }
                else
                {
                    arr[k++] = v2[i2++];
                }
            }
        }

        static void Main(string[] args)
        {
            StreamReader sr = null;
            StreamWriter sw = null;
            try
            {
                sw = new StreamWriter(FileOutputName);
                sr = new StreamReader(FileInputName);
                List<int> list = new List<int>();
                while ( !sr.EndOfStream )
                {
                    string[] sArray = sr.ReadLine().Split(' ');
                    for ( int i = 0; i < sArray.Length; i++ )
                    {
                        list.Add(int.Parse(sArray[i]));
                    }
                }
                int[] arr = new int[list.Count];
                for ( int i = 0; i < list.Count; i++ )
                {
                    arr[i] = list[i];
                }
                mergeSort(arr);
                for ( int i = 0; i < arr.Length; i++ )
                {
                    sw.Write(arr[i]);
                    sw.Write(' ');
                }
            }
            catch ( IOException ex )
            {
                Console.WriteLine("Fehler bei der Dateiverarbeitung!\n" + ex);
            }
            finally
            {
                if ( sr != null )
                {
                    sr.Close();
                }
                if ( sw != null )
                {
                    sw.Close();
                }
            }
        }
    }
}