Differences

This shows you the differences between two versions of the page.

--- fuss:csharp [2017/02/22 18:30] – external edit 127.0.0.1
+++ fuss:csharp [2019/08/22 07:32] – [Recursive] office
@@ Line 1593: / Line 1593: @@
 var o = object.GetFP("Class.Member.Class.Field");
 </code>
+====== Merge Sort ======
+===== Recursive =====
+Recursively and using generics.
+<code csharp>
+using System;
+namespace Sorts.MergeSort.Recursive
+{
+    public class MergeSort
+    {
+        private static int[] List { get; set; }
+        public MergeSort(int[] list)
+        {
+            List = list;
+        }
+        public int[] Sort()
+        {
+            return Partition(List);
+        }
+        private static T[] Partition<T>(T[] list) where T : IComparable
+        {
+            if (list.Length <= 1)
+            {
+                return list;
+            }
+            var pivot = list.Length / 2;
+            T[] l = new T[pivot];
+            Array.Copy(list, 0, l, 0, pivot);
+            T[] r = new T[list.Length - pivot];
+            Array.Copy(list, pivot, r, 0, list.Length - pivot);
+            return Merge(Partition(l), Partition(r));
+        }
+        private static T[] Concatenate<T>(T[] a, T[] b) where T : IComparable
+        {
+            T[] rest = new T[a.Length + b.Length];
+            Array.Copy(a, 0, rest, 0, a.Length);
+            Array.Copy(b, 0, rest, a.Length, b.Length);
+            return rest;
+        }
+        private static T[] Concatenate<T>(T a, T[] l) where T : IComparable
+        {
+            T[] result = new T[l.Length + 1];
+            result[0] = a;
+            Array.Copy(l, 0, result, 1, l.Length);
+            return result;
+        }
+        private static T Car<T>(T[] l) where T : IComparable
+        {
+            return l[0];
+        }
+        private static T[] Cdr<T>(T[] l) where T : IComparable
+        {
+            T[] cdr = new T[l.Length - 1];
+            Array.Copy(l, 1, cdr, 0, l.Length - 1);
+            return cdr;
+        }
+        private static T[] Merge<T>(T[] l, T[] r) where T : IComparable
+        {
+            if (l.Length == 0 || r.Length == 0)
+            {
+                return Concatenate(l, r);
+            }
+            if (l[0].CompareTo(r[0]) > 0)
+            {
+                return Concatenate(Car(r), Merge(l, Cdr(r)));
+            }
+            return Concatenate(Car(l), Merge(Cdr(l), r));
+        }
+    }
+}
+</code>
+May have stack issues so should be called by increasing the stack size:
+<code csharp>
+            var t = new Thread(() =>
+                {
+                    list = new MergeSort.Recursive.MergeSort(list).Sort();
+                }, 1024 * 1024 * 50);
+            t.Start();
+</code>
+===== Iterative =====
+<code csharp>
+using System;
+namespace Sorts.MergeSort.Iterative
+{
+    public class MergeSort
+    {
+        private static int[] List { get; set; }
+        public MergeSort(int[] list)
+        {
+            List = list;
+        }
+        public int[] Sort()
+        {
+            return Sort(List);
+        }
+        private static T Min<T>(T x, T y) where T : IComparable
+        {
+            return x.CompareTo(y) < 0 ? x : y;
+        }
+        private static T[] Sort<T>(T[] a) where T : IComparable
+        {
+            T[] b = new T[a.Length];
+            for (int size = 1; size < a.Length; size *= 2)
+            {
+                for (int left = 0; left + size < a.Length; left += size * 2)
+                {
+                    int l = left + size;
+                    int r = Min(l + size, a.Length);
+                    var k = left;
+                    var i = left;
+                    var j = l;
+                    while (i < l && j < r)
+                    {
+                        if (a[i].CompareTo(a[j]) < 0)
+                        {
+                            b[k] = a[i];
+                            ++i;
+                        }
+                        else
+                        {
+                            b[k] = a[j];
+                            ++j;
+                        }
+                        ++k;
+                    }
+                    while (i < l)
+                    {
+                        b[k] = a[i];
+                        ++i;
+                        ++k;
+                    }
+                    while (j < r)
+                    {
+                        b[k] = a[j];
+                        ++j;
+                        ++k;
+                    }
+                    for (k = left; k < r; ++k)
+                    {
+                        a[k] = b[k];
+                    }
+                }
+            }
+            return a;
+        }
+    }
+}
+</code>