1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
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++];
}
}
}
}
|