-
Notifications
You must be signed in to change notification settings - Fork 266
/
Timsort.c
124 lines (103 loc) · 2.64 KB
/
Timsort.c
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
#include <stdio.h>
const int THRESHOLD = 32;
int is_odd(int n) { return n & 1; }
int get_fmin(int a, int b) {
if (a < b) {
return a;
}
return b;
}
int get_floor(int n) { return n / 2; }
void print_array(int array[], int size) {
printf("[");
for (int i = 0; i < size; i++) {
printf("%d", array[i]);
if (i != size - 1) {
printf(", ");
}
}
printf("]\n");
}
int get_run_length(int size_of_array) {
int run_length = size_of_array;
int remainder = 0;
while (run_length >= THRESHOLD) {
if (is_odd(run_length)) {
remainder = 1;
}
run_length = get_floor(run_length / 2);
}
return run_length + remainder;
}
void insertion_sort(int array[], int left_index, int right_index) {
for (int i = left_index + 1; i <= right_index; i++) {
int temp = array[i];
int j = i - 1;
while (j >= left_index && array[j] > temp) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = temp;
}
}
void merge_runs(int array[], int left_index, int middle_index,
int right_index) {
int left_size = middle_index - left_index + 1;
int right_size = right_index - middle_index;
int left[left_size];
int right[right_size];
for (int i = 0; i < left_size; i++) {
left[i] = array[left_index + i];
}
for (int j = 0; j < right_size; j++) {
right[j] = array[middle_index + 1 + j];
}
int i = 0;
int j = 0;
int k = left_index;
while (i < left_size && j < right_size) {
if (left[i] <= right[j]) {
array[k] = left[i];
i++;
} else {
array[k] = right[j];
j++;
}
k++;
}
while (i < left_size) {
array[k] = left[i];
i++;
k++;
}
while (j < right_size) {
array[k] = right[j];
j++;
k++;
}
}
void timsort(int array[], int size) {
int run_length = get_run_length(size);
for (int i = 0; i < size; i += run_length) {
insertion_sort(array, i, get_fmin((i + run_length - 1), (size - 1)));
}
for (int size_of_run = run_length; size_of_run < size; size_of_run *= 2) {
for (int left_index = 0; left_index < size; left_index += 2 * size_of_run) {
int middle_index = left_index + size_of_run - 1;
int right_index =
get_fmin((left_index + 2 * size_of_run - 1), (size - 1));
merge_runs(array, left_index, middle_index, right_index);
}
}
}
int main() {
int array[] = {5, 2, -2147483648, 1, 4, 5323, -1, 0, 10,
9, 8, 7, 6, 2147483647, 4, 3, 2};
int size = sizeof(array) / sizeof(array[0]);
printf("Original array:\t");
print_array(array, size);
timsort(array, size);
printf("Sorted array:\t");
print_array(array, size);
return 0;
}