using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace ALGA { public class Mergesort { public static void mergesort(ISortList list) { if (list.Count <= 1) return; mergesort(list, 0, list.Count - 1); } public static void mergesort(ISortList list, int leftIndex, int rightIndex) { if (leftIndex > rightIndex) return; if (rightIndex - leftIndex <= 0) return; int middle = (leftIndex + rightIndex) / 2; mergesort(list, leftIndex, middle); mergesort(list, middle + 1, rightIndex); merge(list, leftIndex, middle, rightIndex); } private static void merge(ISortList list, int leftIndex, int middleIndex, int rightIndex) { int leftSize = middleIndex - leftIndex + 1; ISortList left = new SortList(leftSize); for (int i = 0; i < leftSize; i++) left[i] = list[leftIndex + i]; int rightSize = rightIndex - middleIndex; ISortList right = new SortList(rightSize); for (int i = 0; i < rightSize; i++) right[i] = list[middleIndex + 1 + i]; int leftOffset = 0; int rightOffset = 0; for (int i = leftIndex; i <= rightIndex; i++) { if (leftOffset == leftSize) { list[i] = right[rightOffset++]; continue; } if (rightOffset == rightSize) { list[i] = left[leftOffset++]; continue; } if (left[leftOffset] < right[rightOffset]) list[i] = left[leftOffset++]; else list[i] = right[rightOffset++]; } } } }