58 lines
1.8 KiB
C#
58 lines
1.8 KiB
C#
|
namespace SortingVisualization.Algorithms {
|
|||
|
|
public class Mergesort : SortingAlgorithm {
|
|||
|
|
public override string GetAlgorithmName() => "Mergesort";
|
|||
|
|
|
|||
|
|
public override void Sort(ref DataSet set) {
|
|||
|
|
Simulate(ref set);
|
|||
|
|
System.Console.WriteLine("Doing {0}...", this.GetAlgorithmName());
|
|||
|
|
MergeSort(ref set, 0, set.Size - 1);
|
|||
|
|
System.Console.WriteLine("{0} complete!", this.GetAlgorithmName());
|
|||
|
|
if (!set.SimulateMode)
|
|||
|
|
set.FinalizeVideo();
|
|||
|
|
}
|
|||
|
|
public static void MergeSort(ref DataSet set, int l, int r) {
|
|||
|
|
if (l < r) {
|
|||
|
|
int mid = (l / 2) + (r / 2);
|
|||
|
|
MergeSort(ref set, l, mid);
|
|||
|
|
MergeSort(ref set, mid + 1, r);
|
|||
|
|
Merge(ref set, l, mid, r);
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
private static void Merge(ref DataSet set, int l, int m, int r) {
|
|||
|
|
int left = l;
|
|||
|
|
int right = m + 1;
|
|||
|
|
int[] tmp = new int[(r - l) + 1];
|
|||
|
|
int tmpIndex = 0;
|
|||
|
|
|
|||
|
|
while ((left <= m) && (right <= r)) {
|
|||
|
|
if (set.LessThan(left, right)) {
|
|||
|
|
tmp[tmpIndex] = set.ReadOperation(left);
|
|||
|
|
left++;
|
|||
|
|
} else {
|
|||
|
|
tmp[tmpIndex] = set.ReadOperation(right);
|
|||
|
|
right++;
|
|||
|
|
}
|
|||
|
|
tmpIndex++;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
while (left <= m) {
|
|||
|
|
tmp[tmpIndex] = set.ReadOperation(left);
|
|||
|
|
left++;
|
|||
|
|
tmpIndex++;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
while (right <= r) {
|
|||
|
|
tmp[tmpIndex] = set.ReadOperation(right);
|
|||
|
|
right++;
|
|||
|
|
tmpIndex++;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
for (int i = 0; i < tmp.Length; i++) {
|
|||
|
|
set.WriteOperation(l + i, tmp[i]);
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
}
|