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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
|
// SORT. Sort a linear singly-linked list of INTs.
class Sort {
// NODE. A node in a linear singly linked list of INTs.
private static class Node {
private int number; // The INT in the node, duh.
private Node next; // The NODE that follows this one, or NULL.
// Constructor. Initialize a new NODE with NUMBER and NEXT.
private Node(int number, Node next) {
this.number = number;
this.next = next;
}
}
// MAKE NODES. Return a list of NODEs that contains INTs from NUMBERS in order
// of their appearance.
private static Node makeNodes(int... numbers) {
if (numbers.length > 0) {
Node first = new Node(numbers[0], null);
Node last = first;
for (int index = 1; index < numbers.length; index += 1) {
last.next = new Node(numbers[index], null);
last = last.next;
}
return first;
} else {
return null;
}
}
// WRITE NODES. Write the INTs from a list of NODEs in paired square brackets,
// separated by commas, with a newline at the end.
private static void writeNodes(Node nodes) {
System.out.print('[');
if (nodes != null) {
System.out.print(nodes.number);
nodes = nodes.next;
while (nodes != null) {
System.out.print(", ");
System.out.print(nodes.number);
nodes = nodes.next;
}
}
System.out.println(']');
}
// SORT NODES. Sort UNSORTED, a list of NODEs, into nondecreasing order of its
// NUMBER slots, without making new NODEs.
private static Node sortNodes(Node unsorted) {
Node left = null, right = null, sorted = null;
if (unsorted==null || unsorted.next==null) {
//unsorted is either empty or of length 1
return unsorted;
} //Halving phase
else {
int step = 1;
while (unsorted != null) {
Node next = unsorted.next;
if (step % 2 == 0) { //Even case
//Pops out first value and puts into Right
unsorted.next = right;
right = unsorted;
} else { //Odd case
// Pops out first value and puts into Left
unsorted.next = left;
left = unsorted;
}
step++;
unsorted = next;
}
}
//Sorting (recursive) Phase
left = sortNodes(left);
right = sortNodes(right);
//Combining phase
Node end = null;
if (left.number < right.number) {
Node temp = left.next;
sorted=left;
end = left;
left.next = null;
left = temp;
end.next = null;
} else if (right.number > left.number) {
Node temp = right.next;
end = right;
sorted = right;
right.next =null;
right = temp;
end.next = null;
}
while (left != null && right != null) {
if (left.number > right.number) {
right.next = end;
Node temp = right.next;
right.next = null;
end = temp;
} else {
left.next = end;
Node temp = left.next;
left.next = null;
end = temp;
}
}
if (left == null) {
end.next=right;
} else {
end.next=left;
}
return sorted;
}
// MAIN. Run some examples. The comments show what must be printed.
public static void main(String[] args) {
writeNodes(sortNodes(makeNodes())); // []
writeNodes(sortNodes(makeNodes(1))); // [1]
writeNodes(sortNodes(makeNodes(1, 2))); // [1, 2]
writeNodes(sortNodes(makeNodes(2, 1))); // [1, 2]
writeNodes(sortNodes(makeNodes(1, 2, 3, 4, 5, 6, 7, 8, 9)));
// [1, 2, 3, 4, 5, 6, 7, 8, 9]
writeNodes(sortNodes(makeNodes(9, 8, 7, 6, 5, 4, 3, 2, 1)));
// [1, 2, 3, 4, 5, 6, 7, 8, 9]
writeNodes(sortNodes(makeNodes(3, 1, 4, 5, 9, 2, 6, 8, 7)));
// [1, 2, 3, 4, 5, 6, 7, 8, 9]
}
}
|
