//‘‰ό—ΗŒ^ Merge Sort
//  Form‚Ιƒ{ƒ^ƒ“‚QŒΒ, ƒŠƒXƒgƒ{ƒbƒNƒX‚QŒΒ‚π”z’u
//    (button1.Text="ƒf[ƒ^έ’θ", button2.Text="•ΐ‚Ρ‘Φ‚¦")
//  @(listBox1, listBox2)
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace improvedMergeSort
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }
        private int[] data = new int[25];
       
        private void button1_Click(object sender, EventArgs e)
        {
            listBox1.Items.Clear();
            Random R=new Random();
            for (int i = 0; i < data.Length; i++) listBox1.Items.Add(R.Next(1, 100).ToString());
        }
        private void dspData()
        {
            listBox2.Items.Clear();
            for (int i = 0; i < data.Length; i++) listBox2.Items.Add(data[i].ToString());
        }
        private void setData()
        {
            for (int i = 0; i < data.Length; i++)
            {
                listBox1.SelectedIndex = i;
                data[i] = int.Parse(listBox1.SelectedItem.ToString());
            }
            listBox1.SelectedIndex = -1;
        }
        private int moveArray(int[][] a, int k1,int k2,int j, int i1,int i2)
        {
            for (int i = i1; i < i2; i++) a[k2][j++] = a[k1][i];
            return j;
        }
        private void impMergeSort()
        {
            int k1 = 0, k2=1, num = data.Length;
            int[][] temp = new int[2][];
            temp[0] = data; temp[1] = new int[num];
            for (int step = 1; step < num; step *= 2)
            {
                int N2 = 0,j = 0;
                while (N2 < num)
                {
                    int N0 = N2, N1 = N0 + step;
                    if (N1 >= num) { j = moveArray(temp, k1,k2, j, N0, num); break; }
                    N2 = N1 + step; if (N2 > num) N2 = num;
                    int i1 = N0, i2 = N1;
                    while (i1 < N1)
                        if (i2 >= N2) { j = moveArray(temp, k1,k2, j, i1, N1); break; }
                        else temp[k2][j++] = (temp[k1][i1] > temp[k1][i2]) ? temp[k1][i2++] : temp[k1][i1++];
                    j = moveArray(temp, k1, k2, j, i2, N2);
                }
                k2 = k1; k1 = 1 - k1;
            }
            data = temp[k1];
        }
        private void button2_Click(object sender, EventArgs e)
        {
            setData();
            impMergeSort();
            dspData();
        }
        private void Form1_Load(object sender, EventArgs e)
        {
            button1_Click(sender, e);
            
        }

    }
}