排序算法(六)

TimSort | SakuraTears的博客 · · 99 次点击 · · 开始浏览    

前言

我们在上篇文章 排序算法(五)-双调排序 介绍了双调排序,今天我们来看一下另一种排序算法 —— TimSort。

TimSort是Tim Peters发明的一种混合排序,最早是Python语言的内置排序算法。

关于Python内置的TimSort描述可以查看该 文档

关于TimSort的理论基础,可以查看该篇论文 Optimistic Sorting and Information Theoretic Complexity,这篇论文论证了插入排序和归并排序合并后效率提高的可能性,即TimSort的理论基础。

Java自Java 7 后加入TimSort,其实现参考了Python版本的实现,我们可以在JDK源码的util包下找到它,java.util.TimSort,这个class不是public的,我们无法直接调用,只能够通过Java提供的sort方法等间接调用它。

为什么引入了TimSort呢?我们慢慢来看下吧。

正文

TimSort的排序原理

说到排序算法,我们就先来了解下排序算法的基本原理,这样有助于我们更快理解算法本身。

TimSort作为一种混合排序算法,其内部使用了插入排序(准确的说是二分插入排序)和归并排序

根据我们之前说到的,归并排序是一种时间复杂度很平均(O(n * log n) 排序算法,其缺点一个是如果两个序列长度相差较大(一个长序列和一个短序列归并),排序效率无法体现;另一个是当数组长度很小时,归并的效率也不是很高且浪费空间。

对于插入排序,虽然时间复杂度为(O(n^2)),但是较小数据量下,其表现也不错,在一部分数据已经排序的情况下,其表现要更好,而使用插入排序的变种二分插入排序,虽不能减少移动次数,但减少了比较次数。

说到这里,我们再说TimSort基于的一个简单事实:数组中的数据都是部分有序(升序或降序)的。

什么意思呢? 比如 数组[9,8,5,7,3,9,1,3,4,6,0,5,3],可以看到里面部分数据[9,8,5],[1,3,4,6]等等有序。

这对插入排序是十分友好的。

Timsort排序算法可以概括成如下几步:

  1. 把待排数组划分成一个个run,当然run不能太短,长度最小阈值为minRun;
  2. run的划分规则:从数组最小下标low开始,寻找连续有序部分(连续逆序也算,寻找的时候会把这段顺序反过来),如果这段有序部分长度小于minRun,就用二分插入排序补充到minRun;
  3. 将run入栈,当栈顶的run的长度不满足下列约束条件中任意一个时,
    1
    2
    runLen[n-1] > runLen[n] + runLen[n+1]
    runLen[n] > runLen[n+1]
    则利用归并排序将其中最短的2个run合并成一个新run;
  4. 最后会有一次强制合并合并所有栈内剩余所有run,最终栈空,生成有序数组。

TimSort算法的原理可以用下图大致表示:

这儿我们设minRun = 4.

upload successful

如上图可以清晰的看到TimSort的排序过程。

TimSort源码分析

下面我们来分析下TimSort的源码。

它的主要入口为sort方法,sort方法参数说明如下:

T[] a : 表示待排序数组;
int lo:排序的起始位置,如果排整个数组传0即可;
int hi:排序的终止位置,排整个数组传数组长度n即可;
Comparator<? super T> c:数据的比较规则;
T[] work: 合并所需的临时存储空间设置,一般不需要我们设置,会有默认值,传null即可;
int workBase :合并所需的临时存储空间分片基数值,一般不需要我们设置,会有默认值,传0即可;
int workLen:合并所需的临时存储空间默认长度,一般不需要我们设置,会有默认值,传0即可。

upload successful

可以看到传入的排序位置lo和hi,如果长度小于2,直接返回,如果小于32,就做mini-TimSort,迷你TimSort就相当于上面图中说的部分有序的二分插入排序。

再来看下下面部分。

upload successful

TimSort先计算出该数组的minRun,然后开始处理数据,拿到有序长度,判断是否小于minRun,小于的话就用插入排序补齐,然后入栈,看看是否需要进行归并排序,移动位置到下一个run,重复上述过程,最后在进行一次归并排序,得到有序数据。

二分插入排序法的源码如下:

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
private static <T> void binarySort(T[] a, int lo, int hi, int start,Comparator<? super T> c) {
assert lo <= start && start <= hi;
if (start == lo)
start++;
for ( ; start < hi; start++) {
T pivot = a[start];
// Set left (and right) to the index where a[start] (pivot) belongs
int left = lo;
int right = start;
assert left <= right;
/*
* Invariants:
* pivot >= all in [lo, left).
* pivot < all in [right, start).
*/
while (left < right) {
int mid = (left + right) >>> 1;
if (c.compare(pivot, a[mid]) < 0)
right = mid;
else
left = mid + 1;
}
assert left == right;
/*
* The invariants still hold: pivot >= all in [lo, left) and
* pivot < all in [left, start), so pivot belongs at left. Note
* that if there are elements equal to pivot, left points to the
* first slot after them -- that's why this sort is stable.
* Slide elements over to make room for pivot.
*/
int n = start - left; // The number of elements to move
// Switch is just an optimization for arraycopy in default case
switch (n) {
case 2: a[left + 2] = a[left + 1];
case 1: a[left + 1] = a[left];
break;
default: System.arraycopy(a, left, a, left + 1, n);
}
a[left] = pivot;
}
}

计算有序部分长度(如果逆序有序就把数据处理成正序)的源码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi,Comparator<? super T> c) {
assert lo < hi;
int runHi = lo + 1;
if (runHi == hi)
return 1;
// Find end of run, and reverse range if descending
if (c.compare(a[runHi++], a[lo]) < 0) { // Descending
while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)
runHi++;
reverseRange(a, lo, runHi);
} else { // Ascending
while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0)
runHi++;
}
return runHi - lo;
}
private static void reverseRange(Object[] a, int lo, int hi) {
hi--;
while (lo < hi) {
Object t = a[lo];
a[lo++] = a[hi];
a[hi--] = t;
}
}

获取该数组的minRun的相关代码如下:

1
2
3
4
5
6
7
8
9
private static int minRunLength(int n) {
assert n >= 0;
int r = 0; // Becomes 1 if any 1 bits are shifted off
while (n >= MIN_MERGE) {
r |= (n & 1);
n >>= 1;
}
return n + r;
}

可以看到如果入参n小于MIN_MERGE(32)时,会直接返回n,因为太小了;如果n恰好是2的幂,则返回MIN_MERGE/2;否则返回一个int k, MIN_MERGE/2 <= k <= MIN_MERGE,使n/k接近但小于2的幂次值。

关于这样设计的基本原理,可以查看Tim在Python上关于它的描述文档 listsort.txt

检测并合并不符合条件的栈元素的相关代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private void mergeCollapse() {
while (stackSize > 1) {
int n = stackSize - 2;
if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {
if (runLen[n - 1] < runLen[n + 1])
n--;
mergeAt(n);
} else if (runLen[n] <= runLen[n + 1]) {
mergeAt(n);
} else {
break; // Invariant is established
}
}
}

我们可以看到它的合并条件,如上面提到的。

关于它的合并方法mergeAt,内容较多,在这儿就不展示了。

最后强制合并栈元素的代码如下:

1
2
3
4
5
6
7
8
private void mergeForceCollapse() {
while (stackSize > 1) {
int n = stackSize - 2;
if (n > 0 && runLen[n - 1] < runLen[n + 1])
n--;
mergeAt(n);
}
}

该方法最终会将栈内元素合并为1个,即run[0],即有序数组。

初始化栈空间及归并缓存空间代码如下:

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
private TimSort(T[] a, Comparator<? super T> c, T[] work, int workBase, int workLen) {
this.a = a;
this.c = c;
// Allocate temp storage (which may be increased later if necessary)
int len = a.length;
int tlen = (len < 2 * INITIAL_TMP_STORAGE_LENGTH) ?
len >>> 1 : INITIAL_TMP_STORAGE_LENGTH;
if (work == null || workLen < tlen || workBase + tlen > work.length) {
@SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"})
T[] newArray = (T[])java.lang.reflect.Array.newInstance
(a.getClass().getComponentType(), tlen);
tmp = newArray;
tmpBase = 0;
tmpLen = tlen;
}
else {
tmp = work;
tmpBase = workBase;
tmpLen = workLen;
}
int stackLen = (len < 120 ? 5 :
len < 1542 ? 10 :
len < 119151 ? 24 : 49);
runBase = new int[stackLen];
runLen = new int[stackLen];
}

Java版本TimSort曾经的Bug

在JDK1.7时候,TimSort曾经有一个bug,会引发数组下标越界异常。

PS:这个Bug已经被fix了。

bug详情可参考如下链接 JDK-8011944 : Sort fails with ArrayIndexOutOfBoundsException

关于这篇bug的发现验证解决可参考这篇pdf,OpenJDK’s java.utils.Collection.sort() is broken:The good, the bad and the worst case?

我们这儿简单说下这个bug吧。

上面我们看到TimSort栈内元素合并的条件,它的目的在于尽量保证两个要进行归并排序的数组长度大致相同。

所以栈内所有run应该满足如下条件:

1
2
3
2 <= i <= StackSize-1
runLen[n-1] > runLen[n] + runLen[n+1]
runLen[n] > runLen[n+1]

我们看mergeCollapse方法也能验证这一点。

大多数情况下我们检查栈顶的3个元素就能满足约束条件,但是一些特殊情况下就不行了,比如下面的这个栈:

1
120, 80, 25, 20, 30

根据源码,因为25 < 20 + 30,25 < 30,所以将25和20两个run进行合并,此时栈内的情况变为

1
120, 80, 45, 30

由于80 > 45 + 30,45 > 30,满足约束条件,此时归并就终止了。但是注意栈里的其他run,120 < 80 + 45,这是不满足约束条件的,而由于我们只判断了栈顶的run,因此在这里就留下了“隐患”。

大多数情况下,这并不是什么问题,因为TimSort最终可以通过最后的强制归并将数据排序合并。

但是Bug发现者构造了一个非常精致的Array,成功的让Timsort算法抛出java.lang.ArrayIndexOutOfBoundsException,代码如下:

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
public class BreakTimSort {

private static final int MIN=16;
ArrayDeque<Integer> chunks = new ArrayDeque<Integer>();

private static final int BOUND1 = 2*MIN+1;
private static final int BOUND2 = BOUND1+MIN+2;
private static final int BOUND3 = BOUND1+1+BOUND2;
private static final int BOUND4 = BOUND2+1+BOUND3;
private static final int BOUND5 = BOUND3+1+BOUND4;

public int build(int size, int B) {
chunks.addFirst(B);
if (size < BOUND1) {
chunks.addFirst(size);
return size;
}

int asize = (size+2)/2;
if (size >= BOUND2 && asize < BOUND1)
asize = BOUND1;
else if (size >= BOUND3 && asize < BOUND2)
asize = BOUND2;
else if (size >= BOUND4 && asize < BOUND3)
asize = BOUND3;
else if (size >= BOUND5 && asize < BOUND4)
asize = BOUND4;
if (size - asize >= B)
throw new AssertionError( " " +size+ " , " +asize+ " , " +B);
return build (asize, size - asize);
}

public void run() {
chunks.addFirst(MIN);

int B = MIN+4;
int A = B + MIN + 1;

for (int i = 0; i< 8; i++) {
int eps = build(A, B);
B = B+A+1;
A = B+eps + 1;
}
chunks.addFirst(B);
chunks.addFirst(A);
int total = 0;
for (Integer len: chunks) {
total += len;
}
int pow = MIN;
while (pow < total)
pow += pow;
chunks.addLast(pow-total);
System.err.println( " Total: " +total);
Object[] array = new Object[pow];
int off = 0;
int pos = 0;
for (Integer len: chunks) {
for (int i = 0; i < len; i++) {
array[pos++] = Integer.valueOf(i == 0 ? 0 : 1);
}
off++;
}
Arrays.sort(array);
}

public static void main(String[] param) {
new BreakTimSort().run();
}
}

PS:这段代码我们现在测试是没有问题的,因为这个bug已经被Fix了,如果想复现这个bug,可以下载 JDK - 1.7.0_07 版本。

这个bug出现的原因是TimSort初始化时会申请栈空间,如下:

1
2
3
4
5
int stackLen = (len <    120  ?  5 :
len < 1542 ? 10 :
len < 119151 ? 24 : 49);
runBase = new int[stackLen];
runLen = new int[stackLen];

在JDK - 1.7.0_07版本它是这样的:

1
2
3
4
5
int stackLen = (len <    120  ?  5 :
len < 1542 ? 10 :
len < 119151 ? 19 : 40);
runBase = new int[stackLen];
runLen = new int[stackLen];

可以看到有几个数字不一样,是的,不要小看这几个“魔法”数字。

这几个数字怎么来呢? 我们栈归并的条件上面有提到,它其实就是函数 F(n) < F(n-1) + F(n-2) +1,我们设F(n) = F(n-1) + F(n-2) +1,这个函数是不是很熟悉,在 SmoothSort里我们有提到过,不过我们这里的起始是0,第一个元素是minRun。

我们设minRun为16(上面的minRunLength方法,可以看到minRun最小值为MIN_MERGE/2 = 16),如下程序:

PS:minRun越小,数组长度固定的情况下,分的份数就越多,理论需要的栈数量也越多。栈数量要多,少的话可能出现数组下标越界问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private static void getNum(){
int[] k = new int[]{5,10,19,40};
for(int p=0;p<k.length;p++){
long sum =0;
for(int i=0;i<k[p];i++){
sum += function(i);
}
System.out.println(k[p] +"--->"+sum);
}

}
private static long function(long n){
if(n ==0){
return 0;
}else if(n==1){
return 16;
}
return function(n-1) + function(n-2)+1;
}

如下输出:

1
2
3
4
5--->119
10--->1541
19--->119150
40--->2917196495

当为40的时候已经超出了int最大值。

上述数据是在理想情况下,即 F(n) = F(n-1) + F(n-2) +1,但是实际上会有不满足的情况,这时候需要的栈大小就应该大一些,因而就出现了我们上述所说的异常。

关于实际需要的栈大小,上面PDF中给出了,可以直接查看,如下:

array size6412816065536131072671088641073741824
required stack size34521234149
runLen.length5101019 (24)404040

可以看到JDK1.8中长度已经变为了5,10,24,49,相当于修复了这个bug。

上述PDF中还给出了一种出现无法合并的栈的情况的解决方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private void mergeCollapse() {
while (stackSize > 1) {
int n = stackSize - 2;
if (n > 0 && runLen[n-1] <=runLen[n] + runLen[n + 1]
||n-1 > 0 && runLen[n-2] <=runLen[n] + runLen[n-1]){
if (runLen[n-1] <runLen[n + 1]) {
n--;
}
} else if (n < 0 || runLen[n] > runLen[n + 1]) {
break; // Invariant is established
}
mergeAt(n);
}
}

相当于增加了n-1 > 0 && runLen[n-2] <= runLen[n] + runLen[n-1] 这部分,把栈顶的第4个元素也加入了判断。

但是Java社区JDK1.8中并未采用这段代码,还是原来的3层栈元素判断,只是变更了栈的长度作为解决办法,原因不详。

以上就是TimSort曾经出现的bug。

测试TimSort

我们将TimSort源码中的泛型去掉,排序数组改为int[],测试下TimSort的性能。

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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
public class TimSort {

private static final int MIN_MERGE = 32;

private final int[] a;

private static final int MIN_GALLOP = 7;

private int minGallop = MIN_GALLOP;

private static final int INITIAL_TMP_STORAGE_LENGTH = 256;

private int[] tmp;
private int tmpBase;
private int tmpLen;

private int stackSize = 0;
private final int[] runBase;
private final int[] runLen;

private TimSort(int[] a, int[] work, int workBase, int workLen) {
this.a = a;

// Allocate temp storage (which may be increased later if necessary)
int len = a.length;
int tlen = (len < 2 * INITIAL_TMP_STORAGE_LENGTH) ?
len >>> 1 : INITIAL_TMP_STORAGE_LENGTH;
if (work == null || workLen < tlen || workBase + tlen > work.length) {
tmp = new int[tlen];
tmpBase = 0;
tmpLen = tlen;
}
else {
tmp = work;
tmpBase = workBase;
tmpLen = workLen;
}

int stackLen = (len < 120 ? 5 :
len < 1542 ? 10 :
len < 119151 ? 24 : 49);
runBase = new int[stackLen];
runLen = new int[stackLen];
}


static void sort(int[] a, int lo, int hi,int[] work, int workBase, int workLen) {
assert a != null && lo >= 0 && lo <= hi && hi <= a.length;

int nRemaining = hi - lo;
if (nRemaining < 2) {
return; // Arrays of size 0 and 1 are always sorted
}

// If array is small, do a "mini-TimSort" with no merges
if (nRemaining < MIN_MERGE) {
int initRunLen = countRunAndMakeAscending(a, lo, hi);
binarySort(a, lo, hi, lo + initRunLen);
return;
}

TimSort ts = new TimSort(a,work, workBase, workLen);
int minRun = minRunLength(nRemaining);
do {
// Identify next run
int runLen = countRunAndMakeAscending(a, lo, hi);

// If run is short, extend to min(minRun, nRemaining)
if (runLen < minRun) {
int force = nRemaining <= minRun ? nRemaining : minRun;
binarySort(a, lo, lo + force, lo + runLen);
runLen = force;
}

// Push run onto pending-run stack, and maybe merge
ts.pushRun(lo, runLen);
ts.mergeCollapse();

// Advance to find next run
lo += runLen;
nRemaining -= runLen;
} while (nRemaining != 0);

// Merge all remaining runs to complete sort
assert lo == hi;
ts.mergeForceCollapse();
assert ts.stackSize == 1;
}

private static void binarySort(int[] a, int lo, int hi, int start) {
assert lo <= start && start <= hi;
if (start == lo) {
start++;
}
for ( ; start < hi; start++) {
int pivot = a[start];

// Set left (and right) to the index where a[start] (pivot) belongs
int left = lo;
int right = start;
assert left <= right;
/*
* Invariants:
* pivot >= all in [lo, left).
* pivot < all in [right, start).
*/
while (left < right) {
int mid = (left + right) >>> 1;
if (pivot<a[mid]) {
right = mid;
}else {
left = mid + 1;
}
}
assert left == right;

// The number of elements to move
int n = start - left;
// Switch is just an optimization for arraycopy in default case
switch (n) {
case 2: a[left + 2] = a[left + 1];
case 1: a[left + 1] = a[left];
break;
default: System.arraycopy(a, left, a, left + 1, n);
}
a[left] = pivot;
}
}

private static int countRunAndMakeAscending(int[] a, int lo, int hi) {
assert lo < hi;
int runHi = lo + 1;
if (runHi == hi) {
return 1;
}

// Find end of run, and reverse range if descending
// Descending
if (a[runHi++]< a[lo]) {
while (runHi < hi && a[runHi]< a[runHi - 1]) {
runHi++;
}
reverseRange(a, lo, runHi);
// Ascending
} else {
while (runHi < hi && a[runHi]>= a[runHi - 1]) {
runHi++;
}
}

return runHi - lo;
}

private static void reverseRange(int[] a, int lo, int hi) {
hi--;
while (lo < hi) {
int t = a[lo];
a[lo++] = a[hi];
a[hi--] = t;
}
}

private static int minRunLength(int n) {
assert n >= 0;
// Becomes 1 if any 1 bits are shifted off
int r = 0;
while (n >= MIN_MERGE) {
r |= (n & 1);
n >>= 1;
}
return n + r;
}

private void pushRun(int runBase, int runLen) {
this.runBase[stackSize] = runBase;
this.runLen[stackSize] = runLen;
stackSize++;
}

private void mergeCollapse() {
while (stackSize > 1) {
int n = stackSize - 2;
if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {
if (runLen[n - 1] < runLen[n + 1]) {
n--;
}
mergeAt(n);
} else if (runLen[n] <= runLen[n + 1]) {
mergeAt(n);
} else {
break; // Invariant is established
}
}
}

private void mergeForceCollapse() {
while (stackSize > 1) {
int n = stackSize - 2;
if (n > 0 && runLen[n - 1] < runLen[n + 1]) {
n--;
}
mergeAt(n);
}
}

private void mergeAt(int i) {
assert stackSize >= 2;
assert i >= 0;
assert i == stackSize - 2 || i == stackSize - 3;

int base1 = runBase[i];
int len1 = runLen[i];
int base2 = runBase[i + 1];
int len2 = runLen[i + 1];
assert len1 > 0 && len2 > 0;
assert base1 + len1 == base2;

runLen[i] = len1 + len2;
if (i == stackSize - 3) {
runBase[i + 1] = runBase[i + 2];
runLen[i + 1] = runLen[i + 2];
}
stackSize--;

int k = gallopRight(a[base2], a, base1, len1, 0);
assert k >= 0;
base1 += k;
len1 -= k;
if (len1 == 0) {
return;
}

len2 = gallopLeft(a[base1 + len1 - 1], a, base2, len2, len2 - 1);
assert len2 >= 0;
if (len2 == 0) {
return;
}

// Merge remaining runs, using tmp array with min(len1, len2) elements
if (len1 <= len2) {
mergeLo(base1, len1, base2, len2);
}else {
mergeHi(base1, len1, base2, len2);
}
}

private static int gallopLeft(int key, int[] a, int base, int len, int hint) {
assert len > 0 && hint >= 0 && hint < len;
int lastOfs = 0;
int ofs = 1;
if (key> a[base + hint]) {
// Gallop right until a[base+hint+lastOfs] < key <= a[base+hint+ofs]
int maxOfs = len - hint;
while (ofs < maxOfs && key> a[base + hint + ofs]) {
lastOfs = ofs;
ofs = (ofs << 1) + 1;
// int overflow
if (ofs <= 0) {
ofs = maxOfs;
}
}
if (ofs > maxOfs) {
ofs = maxOfs;
}

// Make offsets relative to base
lastOfs += hint;
ofs += hint;
} else { // key <= a[base + hint]
// Gallop left until a[base+hint-ofs] < key <= a[base+hint-lastOfs]
final int maxOfs = hint + 1;
while (ofs < maxOfs && key<= a[base + hint - ofs]) {
lastOfs = ofs;
ofs = (ofs << 1) + 1;
// int overflow
if (ofs <= 0) {
ofs = maxOfs;
}
}
if (ofs > maxOfs) {
ofs = maxOfs;
}

// Make offsets relative to base
int tmp = lastOfs;
lastOfs = hint - ofs;
ofs = hint - tmp;
}
assert -1 <= lastOfs && lastOfs < ofs && ofs <= len;

lastOfs++;
while (lastOfs < ofs) {
int m = lastOfs + ((ofs - lastOfs) >>> 1);

if (key> a[base + m]) {
// a[base + m] < key
lastOfs = m + 1;
}else {
// key <= a[base + m]
ofs = m;
}
}
// so a[base + ofs - 1] < key <= a[base + ofs]
assert lastOfs == ofs;
return ofs;
}

private static int gallopRight(int key, int[] a, int base, int len,int hint) {
assert len > 0 && hint >= 0 && hint < len;

int ofs = 1;
int lastOfs = 0;
if (key< a[base + hint]) {
// Gallop left until a[b+hint - ofs] <= key < a[b+hint - lastOfs]
int maxOfs = hint + 1;
while (ofs < maxOfs && key< a[base + hint - ofs]) {
lastOfs = ofs;
ofs = (ofs << 1) + 1;
// int overflow
if (ofs <= 0) {
ofs = maxOfs;
}
}
if (ofs > maxOfs) {
ofs = maxOfs;
}

// Make offsets relative to b
int tmp = lastOfs;
lastOfs = hint - ofs;
ofs = hint - tmp;
} else { // a[b + hint] <= key
// Gallop right until a[b+hint + lastOfs] <= key < a[b+hint + ofs]
int maxOfs = len - hint;
while (ofs < maxOfs && key>= a[base + hint + ofs]) {
lastOfs = ofs;
ofs = (ofs << 1) + 1;
// int overflow
if (ofs <= 0) {
ofs = maxOfs;
}
}
if (ofs > maxOfs) {
ofs = maxOfs;
}

// Make offsets relative to b
lastOfs += hint;
ofs += hint;
}
assert -1 <= lastOfs && lastOfs < ofs && ofs <= len;

lastOfs++;
while (lastOfs < ofs) {
int m = lastOfs + ((ofs - lastOfs) >>> 1);

if (key< a[base + m]) {
// key < a[b + m]
ofs = m;
}else {
// a[b + m] <= key
lastOfs = m + 1;
}
}
// so a[b + ofs - 1] <= key < a[b + ofs]
assert lastOfs == ofs;
return ofs;
}

private void mergeLo(int base1, int len1, int base2, int len2) {
assert len1 > 0 && len2 > 0 && base1 + len1 == base2;

// Copy first run into temp array
// For performance
int[] a = this.a;
int[] tmp = ensureCapacity(len1);
// Indexes into tmp array
int cursor1 = tmpBase;
// Indexes int a
int cursor2 = base2;
// Indexes int a
int dest = base1;
System.arraycopy(a, base1, tmp, cursor1, len1);

// Move first element of second run and deal with degenerate cases
a[dest++] = a[cursor2++];
if (--len2 == 0) {
System.arraycopy(tmp, cursor1, a, dest, len1);
return;
}
if (len1 == 1) {
System.arraycopy(a, cursor2, a, dest, len2);
// Last elt of run 1 to end of merge
a[dest + len2] = tmp[cursor1];
return;
}

int minGallop = this.minGallop;
outer:
while (true) {
// Number of times in a row that first run won
int count1 = 0;
// Number of times in a row that second run won
int count2 = 0;

do {
assert len1 > 1 && len2 > 0;
if (a[cursor2]< tmp[cursor1]) {
a[dest++] = a[cursor2++];
count2++;
count1 = 0;
if (--len2 == 0) {
break outer;
}
} else {
a[dest++] = tmp[cursor1++];
count1++;
count2 = 0;
if (--len1 == 1) {
break outer;
}
}
} while ((count1 | count2) < minGallop);

do {
assert len1 > 1 && len2 > 0;
count1 = gallopRight(a[cursor2], tmp, cursor1, len1, 0);
if (count1 != 0) {
System.arraycopy(tmp, cursor1, a, dest, count1);
dest += count1;
cursor1 += count1;
len1 -= count1;
// len1 == 1 || len1 == 0
if (len1 <= 1) {
break outer;
}
}
a[dest++] = a[cursor2++];
if (--len2 == 0) {
break outer;
}

count2 = gallopLeft(tmp[cursor1], a, cursor2, len2, 0);
if (count2 != 0) {
System.arraycopy(a, cursor2, a, dest, count2);
dest += count2;
cursor2 += count2;
len2 -= count2;
if (len2 == 0) {
break outer;
}
}
a[dest++] = tmp[cursor1++];
if (--len1 == 1) {
break outer;
}
minGallop--;
} while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP);
if (minGallop < 0) {
minGallop = 0;
}
// Penalize for leaving gallop mode
minGallop += 2;
} // End of "outer" loop
// Write back to field
this.minGallop = minGallop < 1 ? 1 : minGallop;

if (len1 == 1) {
assert len2 > 0;
System.arraycopy(a, cursor2, a, dest, len2);
// Last elt of run 1 to end of merge
a[dest + len2] = tmp[cursor1];
} else if (len1 == 0) {
throw new IllegalArgumentException(
"Comparison method violates its general contract!");
} else {
assert len2 == 0;
assert len1 > 1;
System.arraycopy(tmp, cursor1, a, dest, len1);
}
}


private void mergeHi(int base1, int len1, int base2, int len2) {
assert len1 > 0 && len2 > 0 && base1 + len1 == base2;

// Copy second run into temp array
// For performance
int[] a = this.a;
int[] tmp = ensureCapacity(len2);
int tmpBase = this.tmpBase;
System.arraycopy(a, base2, tmp, tmpBase, len2);
// Indexes into a
int cursor1 = base1 + len1 - 1;
// Indexes into tmp array
int cursor2 = tmpBase + len2 - 1;
// Indexes into a
int dest = base2 + len2 - 1;

// Move last element of first run and deal with degenerate cases
a[dest--] = a[cursor1--];
if (--len1 == 0) {
System.arraycopy(tmp, tmpBase, a, dest - (len2 - 1), len2);
return;
}
if (len2 == 1) {
dest -= len1;
cursor1 -= len1;
System.arraycopy(a, cursor1 + 1, a, dest + 1, len1);
a[dest] = tmp[cursor2];
return;
}

int minGallop = this.minGallop;
outer:
while (true) {
// Number of times in a row that first run won
int count1 = 0;
// Number of times in a row that second run won
int count2 = 0;

do {
assert len1 > 0 && len2 > 1;
if (tmp[cursor2]< a[cursor1]) {
a[dest--] = a[cursor1--];
count1++;
count2 = 0;
if (--len1 == 0) {
break outer;
}
} else {
a[dest--] = tmp[cursor2--];
count2++;
count1 = 0;
if (--len2 == 1) {
break outer;
}
}
} while ((count1 | count2) < minGallop);

do {
assert len1 > 0 && len2 > 1;
count1 = len1 - gallopRight(tmp[cursor2], a, base1, len1, len1 - 1);
if (count1 != 0) {
dest -= count1;
cursor1 -= count1;
len1 -= count1;
System.arraycopy(a, cursor1 + 1, a, dest + 1, count1);
if (len1 == 0) {
break outer;
}
}
a[dest--] = tmp[cursor2--];
if (--len2 == 1) {
break outer;
}

count2 = len2 - gallopLeft(a[cursor1], tmp, tmpBase, len2, len2 - 1);
if (count2 != 0) {
dest -= count2;
cursor2 -= count2;
len2 -= count2;
System.arraycopy(tmp, cursor2 + 1, a, dest + 1, count2);
// len2 == 1 || len2 == 0
if (len2 <= 1) {
break outer;
}
}
a[dest--] = a[cursor1--];
if (--len1 == 0) {
break outer;
}
minGallop--;
} while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP);
if (minGallop < 0) {
minGallop = 0;
}
// Penalize for leaving gallop mode
minGallop += 2;
} // End of "outer" loop
// Write back to field
this.minGallop = minGallop < 1 ? 1 : minGallop;

if (len2 == 1) {
assert len1 > 0;
dest -= len1;
cursor1 -= len1;
System.arraycopy(a, cursor1 + 1, a, dest + 1, len1);
// Move first elt of run2 to front of merge
a[dest] = tmp[cursor2];
} else if (len2 == 0) {
throw new IllegalArgumentException(
"Comparison method violates its general contract!");
} else {
assert len1 == 0;
assert len2 > 0;
System.arraycopy(tmp, tmpBase, a, dest - (len2 - 1), len2);
}
}

private int[] ensureCapacity(int minCapacity) {
if (tmpLen < minCapacity) {
// Compute smallest power of 2 > minCapacity
int newSize = minCapacity;
newSize |= newSize >> 1;
newSize |= newSize >> 2;
newSize |= newSize >> 4;
newSize |= newSize >> 8;
newSize |= newSize >> 16;
newSize++;

// Not bloody likely!
if (newSize < 0) {
newSize = minCapacity;
}else {
newSize = Math.min(newSize, a.length >>> 1);
}

tmp = new int[newSize];
tmpLen = newSize;
tmpBase = 0;
}
return tmp;
}

public static void main(String[] args) {
int[] a = new int[100000000];
Random r = new Random();
for (int i = 0; i < a.length; i++) {
a[i] = r.nextInt(100000000);
}
System.out.println("TimSort排序开始:");
long start = System.currentTimeMillis();
sort(a,0,a.length,null,0,0);
System.out.println("TimSort耗时:"+(System.currentTimeMillis()-start)+"ms");
System.out.println("TimSort排序完成!");
System.out.println("数组是否有序:"+isOrdered(a));
}
}

有如下结果,排序1亿数据耗时在17s左右。

1
2
3
4
TimSort排序开始:
TimSort耗时:17831ms
TimSort排序完成!
数组是否有序:true

TimSort的时间复杂度如下:

  • 时间复杂度(最好):O(n)
  • 时间复杂度(平均):O(n * log n)
  • 时间复杂度(最差):O(n * log n)

TimSort的空间复杂度:O(n)

TimSort是一种稳定排序算法。

TimSort之所以能成为Java的内置排序算法之一,除了其优秀的性能,另一点就在于它的稳定性了。

我们可以对大量随机数据进行测试,虽然TimSort和快排(或者其变种)具有相同的时间复杂度【平均 O(n * log n)】,但实际数据显示快排还是要快一些的。

但是快排的缺点是它的不稳定性,比如100个人按名字进行排序,有两个叫张三的,张三(1)无序下是在张三(2)之前的,快排完后可能他们的顺序就变化了,这在某些情况下可能会有问题。

我们来看下TimSort排序动图:

upload successful

图中可以清晰的看到TimSort的排序过程。

其他

在util包下除了TimSort,我们还可以看到一个类 ComparableTimSort,它是针对未实现 Comparator 接口的数据的排序版本,如Object[]。

我们对于一个int[] a,调用数组的 Arrays.sort(a),会使用TimSort吗?

答案是否定的,对于一些基本数据类型数组,两个相同的数的前后顺序不会造成任何影响,所以Arrays.sort(a)里使用了另一种更快速的排序算法DualPivotQuicksort。

我们有时间再看一下DualPivotQuicksort这个排序。

总结

本篇文章通过对TimSort的分析,了解了TimSort的工作运行原理,对Java内置的排序算法有了更深的了解。

后面我们将看下Java的sort接口实现,看看Java内部是如何进一步优化排序,提高效率的。

参考

源码地址

上述文中涉及到的代码可见于我的 GitHub

本文来自:TimSort | SakuraTears的博客

感谢作者:TimSort | SakuraTears的博客

查看原文:排序算法(六)

99 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传