Mergesort (arrays and lists)

Algorithm

1. Divide the given unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
2. Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

Top-Down Approach

Basically the given list is split into sub-lists, until the run size is '1'. And then each sublist is merged to produce sorted list. Below is the c# version of top-down approach:

 

Code Snippet

14. void TopDownMergesort(int[] a)
15.         {
16.             a.ThrowIfNull("a");
17.             int[] t = new int[a.Length];
18.             this.TopDownMergesort(a, t, 0, a.Length - 1);
19.         }
20.         void TopDownMergesort(int[] a, int[] temp, int start, int end)
21.         {
22.             if(start==end)
23.             {
24.                 //run size of '1'
25.                 return;
26.             }
27.             int mid = (start + end) / 2;
28.             this.TopDownMergesort(a, temp, start, mid);
29.             this.TopDownMergesort(a, temp, mid + 1, end);
30.             this.Merge(a, start, mid, end, temp);
31.             for(int i = start;i<=end;i++)
32.             {
33.                 a[i] = temp[i];
34.             }
35.         }
36.         void Merge(int[] a, int start, int mid, int end, int[] temp)
37.         {
38.             int i = start, j = mid+1, k = start;
39.             while((i<=mid) && (j<=end))
40.             {
41.                 if(a[i] <= a[j])
42.                 {
43.                     temp[k] = a[i];
44.                     i++;
45.                 }
46.                 else
47.                 {
48.                     temp[k] = a[j];
49.                     j++;
50.                 }
51.                 k++;
52.             }
53.             while(i<=mid)
54.             {
55.                 temp[k] = a[i];
56.                 i++;
57.                 k++;
58.             }
59.             while (j <= end)
60.             {
61.                 temp[k] = a[j];
62.                 j++;
63.                 k++;
64.             }
65.             Assert.IsTrue(k == end+1);
66.             Assert.IsTrue(i == mid+1);
67.             Assert.IsTrue(j == end+1);
68.         }

 

Bottom-Up Approach

 

Code Snippet

69. void BottomUpMergesort(int[] a)
70.         {
71.             int[] temp = new int[a.Length];
72.             for (int runWidth = 1; runWidth < a.Length; runWidth = 2 * runWidth)
73.             {
74.                 for (int eachRunStart = 0; eachRunStart < a.Length;
75.                     eachRunStart = eachRunStart + 2 * runWidth)
76.                 {
77.                     int start = eachRunStart;
78.                     int mid = eachRunStart + (runWidth - 1);
79.                     if(mid >= a.Length)
80.                     {
81.                         mid = a.Length - 1;
82.                     }
83.                     int end = eachRunStart + ((2 * runWidth) - 1);
84.                     if(end >= a.Length)
85.                     {
86.                         end = a.Length - 1;
87.                     }
88.                     
89.                     this.Merge(a, start, mid, end, temp);
90.                 }
91.                 for (int i = 0; i < a.Length; i++)
92.                 {
93.                     a[i] = temp[i];
94.                 }
95.             }
96.         }        

Merging sorted lists (iterative)

Code Snippet

14. LinkedListADTNode<int> MergeSortedLists(LinkedListADTNode<int> l1, LinkedListADTNode<int> l2)
15.         {
16.             if(l1 == null)
17.             {
18.                 return l2;
19.             }
20.             if(l2 == null)
21.             {
22.                 return l2;
23.             }
24.             var i1 = l1; var i2 = l2;
25.             LinkedListADTNode<int> firstNodeOfMergedList = null, currentNodeOfMergedList = null;
26.             while((i1 != null) && (i2 != null))
27.             {
28.                 LinkedListADTNode<int> temp = null;
29.                 if(i1.Element <= i2.Element)
30.                 {
31.                     temp = i1;
32.                     i1 = temp.Next;
33.                 }
34.                 else
35.                 {
36.                     temp = i2;
37.                     i2 = i2.Next;
38.                 }
39.                 if(firstNodeOfMergedList == null)
40.                 {
41.                     firstNodeOfMergedList = temp;
42.                 }
43.                 else
44.                 {
45.                     currentNodeOfMergedList.Next = temp;
46.                 }
47.                 currentNodeOfMergedList = temp;
48.             }
49.             while(i1 != null)
50.             {
51.                 currentNodeOfMergedList.Next = i1;
52.                 i1 = i1.Next;
53.                 currentNodeOfMergedList = currentNodeOfMergedList.Next;
54.             }
55.             while(i2 != null)
56.             {
57.                 currentNodeOfMergedList.Next = i2;
58.                 i2 = i2.Next;
59.                 currentNodeOfMergedList = currentNodeOfMergedList.Next;
60.             }
61.             return firstNodeOfMergedList;   
62.         }

Merging sorted lists (recursive)

Code Snippet

63. LinkedListADTNode<int> MergeSortedListsRecursive(LinkedListADTNode<int> l1, LinkedListADTNode<int> l2)
64.         {
65.             if(l1 == null)
66.             {
67.                 return l2;
68.             }
69.             if(l2 == null)
70.             {
71.                 return l1;
72.             }
73.             LinkedListADTNode<int> mergedList = null;
74.             if(l1.Element <= l2.Element)
75.             {
76.                 mergedList = l1;
77.                 mergedList.Next = this.MergeSortedListsRecursive(l1.Next, l2);
78.                 
79.             }
80.             else
81.             {
82.                 mergedList = l2;
83.                 mergedList.Next = this.MergeSortedListsRecursive(l1, l2.Next);
84.             }
85.             return mergedList;
86.         }

Unit Tests

Code Snippet

143. [TestMethod]
144.         public void MergeSortedListsTests()
145.         {
146.             LinkedListADT_Int l1 = new LinkedListADT_Int();
147.             LinkedListADT_Int l2 = new LinkedListADT_Int();
148.             for (int i = 1; i <= 15; i++)
149.             {
150.                 if (i % 2 != 0)
151.                 {
152.                     l1.Add(i);
153.                 }
154.                 else
155.                 {
156.                     l2.Add(i);
157.                 }
158.             }
159.             var ml = this.MergeSortedLists(l1.first, l2.first);
160.             var mi = ml;
161.             for (int i = 1; i <= 15; i++)
162.             {
163.                 Assert.IsTrue(mi.Element == i);
164.                 mi = mi.Next;
165.             }
166.             Assert.IsNull(mi);
167.             mi = ml = this.MergeSortedLists(null, l2.first);
168.             Assert.IsNotNull(ml);
169.             for (var i = l2.first; i != null; i = i.Next)
170.             {
171.                 Assert.IsTrue(mi.Element == i.Element);
172.                 mi = mi.Next;
173.             }
174.             Assert.IsNull(mi);
175.             mi = ml = this.MergeSortedLists(l1.first, new LinkedListADTNode<int>(6));
176.             Assert.IsNotNull(ml);
177.         }

Code Snippet

98. [TestMethod]
99.         public void TopToBottomMergesortTests()
100.         {
101.             int[] a = { 13, 4, 1, 3, 8, 11, 9, 10 };
102.             this.TopDownMergesort(a);
103.             int[] b = { 1, 3, 4, 8, 9, 10, 11, 13 };
104.             Assert.IsTrue(a.Length == b.Length);
105.             for(int i = 0;i<a.Length;i++)
106.             {
107.                 Assert.IsTrue(a[i] == b[i]);
108.             }
109.             List<int> l = new List<int>();
110.             for(int i = 10; i>=1; i--)
111.             {
112.                 l.Add(i);
113.             }
114.             var la = l.ToArray();
115.             this.TopDownMergesort(la);
116.             for(int i =1; i<=10; i++)
117.             {
118.                 Assert.IsTrue(la[i - 1] == i);
119.             }
120.         }
121.         [TestCategory(Constants.Arrays_Sorting)]
122.         [TestMethod]
123.         public void BottomUpMergesortTests()
124.         {
125.             int[] a = { 13, 4, 1, 3, 8, 11, 9, 10 };
126.             this.BottomUpMergesort(a);
127.             int[] b = { 1, 3, 4, 8, 9, 10, 11, 13 };
128.             Assert.IsTrue(a.Length == b.Length);
129.             for (int i = 0; i < a.Length; i++)
130.             {
131.                 Assert.IsTrue(a[i] == b[i]);
132.             }
133.             List<int> l = new List<int>();
134.             for (int i = 10; i >= 1; i--)
135.             {
136.                 l.Add(i);
137.             }
138.             var la = l.ToArray();
139.             this.BottomUpMergesort(la);
140.             for (int i = 1; i <= 10; i++)
141.             {
142.                 Assert.IsTrue(la[i - 1] == i);
143.             }
144.             l.Clear();
145.             for (int i = 16; i >= 1; i--)
146.             {
147.                 l.Add(i);
148.             }
149.             la = l.ToArray();
150.             this.BottomUpMergesort(la);
151.             for (int i = 1; i <= l.Count; i++)
152.             {
153.                 Assert.IsTrue(la[i - 1] == i);
154.             }
155.         }

Reference(s)

http://en.wikipedia.org/wiki/Merge_sort#Natural_merge_sort