-
Notifications
You must be signed in to change notification settings - Fork 1
/
mergeSort.cpp
65 lines (58 loc) · 1.41 KB
/
mergeSort.cpp
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
#include <iostream>
#include <vector>
#include <cstdio>
// definition of a record
template <typename Record>
struct Node {
Record entry;
Node<Record> *next;
Node<Record>(): entry(0), next(NULL) {}
Node<Record>(Record v): entry(v), next(NULL) {}
};
template <typename Record>
void mergeSort(Node<Record>* &sublist) {
if (sublist != NULL && sublist->next != NULL) {
Node<Record>* secondlist = divide_from(sublist);
mergeSort(sublist);
mergeSort(secondlist);
sublist = merge(sublist, secondlist);
}
}
template <typename Record>
Node<Record>* divide_from(Node<Record>* &sublist) {
Node<Record> *pos, *mid, *secondlist;
if ((mid = sublist) == NULL) return NULL;
pos = mid->next;
while (pos != NULL) {
pos = pos->next;
if (pos != NULL) {
mid = mid->next;
pos = pos->next;
}
}
secondlist = mid->next;
mid->next = NULL;
return secondlist;
}
template <typename Record>
Node<Record>* merge(Node<Record>* &first, Node<Record>* &second) {
Node<Record>* last;
Node<Record> combined; // zombie node
last = &combined;
while (first != NULL && second != NULL) {
if (first->entry <= second->entry) {
last->next = first;
last = first;
first = first->next;
} else {
last->next = second;
last = second;
second = second->next;
}
}
if (first == NULL)
last->next = second;
else
last->next = first;
return combined.next;
}