Merge sort

By Sep 07, 2015

Description:

Merge sort

Preferencesoft

Merge Sort Algorithm

To sort the elements of an array or list there are many algorithms whose performance varies depending on the number of elements and the positioning of these elements the relative to each other. Merge sort is an algorithm that is to cut an array in half, to recursively call the algorithm on each sub-arrays and merge sub-arrays when they have only a single element. From a performance perspective, merge sort is pretty fast compared to other sorts but not the fastest especially on random tables. However, the algorithm runs in the order of O (n log (n)) as the size n of the array tend to infinity, what seems acceptable. But generally the performance are reduced because very many reservations memory necessary to merge. Another problem is that of recursion which increases the size of the stack for each call.

So let's do a non-recursive merge sort by cutting the initial array in monotonous sub-arrays. Are monotonous sub-arrays trained if possible of 3 items or more. For this, let's browse through the array, taking 3 consecutive elements. If they are in ascending or descending order, we determine the largest monotonous sequence. When these three elements are not in order, we'll sort them. Finally, place possibly the last elements in an array by sorting them.

Program in CSharp

int[] array_aux;
  private void Merge(ref int[] array_a, int b, int m, int e)
        {
            int l = e - b;
            int i = b;
            int j = m;
            for (int k = 0; k < l; k++)
            {
                if ((i < m) && (j < e))
                {
                    if (array_a[i] <= array_a[j])
                    {
                        array_aux[k] = array_a[i];
                        i++;
                    }
                    else
                    {
                        array_aux[k] = array_a[j];
                        j++;
                    }
                }
                else
                {
                    if (i < m)
                    {
                        array_aux[k] = array_a[i];
                        i++;
                    }
                    else
                    {
                        array_aux[k] = array_a[j];
                        j++;
                    }
                }
            }
            for (int k = 0; k < l; k++) array_a[b + k] = array_aux[k];
        }

        private int[] MonotoneSort(ref int[] array_a)
        {
            int l = array_a.Length;
            int[] array_b = new int[l];
            List<int> list_i = new List<int>();
            int i = 0;
            int j = 0;
            int k = 0;
            array_aux = new int[l];
            while (i + 2 < l)
            {
                if (array_a[i] <= array_a[i + 1])
                {
                    if (array_a[i + 1] <= array_a[i + 2])
                    {
                        j = i + 3;
                        bool increasing = true;
                        while (j < l && increasing)
                        {
                            if (array_a[j - 1] > array_a[j])
                            {
                                increasing = false;
                            }
                            else j++;
                        }
                        for (int p = i; p < j; p++)
                        {
                            array_b[k] = array_a[p];
                            k++;
                        }
                        i = j;
                    }
                    else
                    {
                        if (array_a[i] <= array_a[i + 2])
                        {
                            array_b[k] = array_a[i];
                            k++;
                            array_b[k] = array_a[i + 2];
                        }
                        else
                        {
                            array_b[k] = array_a[i + 2];
                            k++;
                            array_b[k] = array_a[i];
                        }
                        k++;
                        array_b[k] = array_a[i + 1];
                        k++;
                        i += 3;
                    }
                }
                else
                {
                    if (array_a[i + 1] >= array_a[i + 2])
                    {
                        j = i + 3;
                        bool decreasing = true;
                        while (j < l && decreasing)
                        {
                            if (array_a[j - 1] < array_a[j])
                            {
                                decreasing = false;
                            }
                            else j++;
                        }
                        for (int p = i; p < j; p++)
                        {
                            array_b[k] = array_a[i + j - 1 - p];
                            k++;
                        }
                        i = j;
                    }
                    else
                    {
                        array_b[k] = array_a[i + 1];
                        k++;
                        if (array_a[i] <= array_a[i + 2])
                        {
                            array_b[k] = array_a[i];
                            k++;
                            array_b[k] = array_a[i + 2];
                        }
                        else
                        {
                            array_b[k] = array_a[i + 2];
                            k++;
                            array_b[k] = array_a[i];
                        }
                        k++;
                        i += 3;
                    }
                }
                list_i.Add(k);
            }
            if (i < l)
            {
                if (i + 1 < l)
                {
                    if (array_a[i] <= array_a[i + 1])
                    {
                        array_b[k] = array_a[i];
                        k++;
                        i++;
                        array_b[k] = array_a[i];
                    }
                    else
                    {
                        array_b[k] = array_a[i + 1];
                        k++;
                        array_b[k] = array_a[i];
                    }
                    k++;
                }
                else
                {
                    array_b[k] = array_a[i];
                    k++;
                }
                list_i.Add(k);
            }
            int n = list_i.Count;
            while (n > 1)
            {
                int a = 0;
                int b = 0;
                int pred = 0;
                int old_n = n;
                while (a + 1 < old_n)
                {
                    Merge(ref array_b, pred, list_i[a], list_i[a + 1]);
                    a++;
                    pred = list_i[a];
                    list_i[b] = list_i[a];
                    b++;
                    a++;
                    n--;
                }
                if (a < old_n)
                {
                    list_i[b] = list_i[a];
                }
            }
            return array_b;
        }
private void button_Click(object sender, RoutedEventArgs e)
        {
            Random rand = new Random();
            int lo = 5000000;
            int[] array_a = new int[lo];
            for (int m = 0; m < lo; m++)
            {
                array_a[m] = rand.Next(2000);
            }
            int[] array_b = MonotoneSort(ref array_a);
        }
    }

CSharp

Categories

Share

Follow


KodFor Privacy Policy