git

1
#include "git-compat-util.h"
2

3
/*
4
 * A merge sort implementation, simplified from the qsort implementation
5
 * by Mike Haertel, which is a part of the GNU C Library.
6
 */
7

8
static void msort_with_tmp(void *b, size_t n, size_t s,
9
			   int (*cmp)(const void *, const void *),
10
			   char *t)
11
{
12
	char *tmp;
13
	char *b1, *b2;
14
	size_t n1, n2;
15

16
	if (n <= 1)
17
		return;
18

19
	n1 = n / 2;
20
	n2 = n - n1;
21
	b1 = b;
22
	b2 = (char *)b + (n1 * s);
23

24
	msort_with_tmp(b1, n1, s, cmp, t);
25
	msort_with_tmp(b2, n2, s, cmp, t);
26

27
	tmp = t;
28

29
	while (n1 > 0 && n2 > 0) {
30
		if (cmp(b1, b2) <= 0) {
31
			memcpy(tmp, b1, s);
32
			tmp += s;
33
			b1 += s;
34
			--n1;
35
		} else {
36
			memcpy(tmp, b2, s);
37
			tmp += s;
38
			b2 += s;
39
			--n2;
40
		}
41
	}
42
	if (n1 > 0)
43
		memcpy(tmp, b1, n1 * s);
44
	memcpy(b, t, (n - n2) * s);
45
}
46

47
void git_stable_qsort(void *b, size_t n, size_t s,
48
		      int (*cmp)(const void *, const void *))
49
{
50
	const size_t size = st_mult(n, s);
51
	char *tmp;
52

53
	tmp = xmalloc(size);
54
	msort_with_tmp(b, n, s, cmp, tmp);
55
	free(tmp);
56
}
57