octave-kai/gnulib-hg: lib/array-mergesort.h annotate

annotate lib/array-mergesort.h @ 17342:c75939cb6254

merge with default branch

author	Michael Goffioul <michael.goffioul@gmail.com>
date	Thu, 21 Feb 2013 14:57:31 +0000
parents	e542fd46ad6f
children

rev	line source
11167 d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	1 /* Stable-sorting of an array using mergesort.
17249 e542fd46ad6f maint: update all copyright year number ranges Eric Blake <eblake@redhat.com> parents: 16201 diff changeset	2 Copyright (C) 2009-2013 Free Software Foundation, Inc.
11167 d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	3 Written by Bruno Haible <bruno@clisp.org>, 2009.
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	4
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	5 This program is free software: you can redistribute it and/or modify it
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	6 under the terms of the GNU Lesser General Public License as published
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	7 by the Free Software Foundation; either version 3 of the License, or
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	8 (at your option) any later version.
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	9
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	10 This program is distributed in the hope that it will be useful,
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	11 but WITHOUT ANY WARRANTY; without even the implied warranty of
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	13 Lesser General Public License for more details.
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	14
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	15 You should have received a copy of the GNU Lesser General Public License
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	16 along with this program. If not, see <http://www.gnu.org/licenses/>. */
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	17
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	18 /* This file implements stable sorting of an array, using the mergesort
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	19 algorithm.
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	20 Worst-case running time for an array of length N is O(N log N).
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	21 Unlike the mpsort module, the algorithm here attempts to minimize not
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	22 only the number of comparisons, but also the number of copying operations.
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	23
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	24 Before including this file, you need to define
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	25 ELEMENT The type of every array element.
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	26 COMPARE A two-argument macro that takes two 'const ELEMENT *'
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	27 pointers and returns a negative, zero, or positive 'int'
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	28 value if the element pointed to by the first argument is,
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	29 respectively, less, equal, or greater than the element
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	30 pointed to by the second argument.
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	31 STATIC The storage class of the functions being defined.
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	32 Before including this file, you also need to include:
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	33 #include <stddef.h>
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	34 */
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	35
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	36 /* Merge the sorted arrays src1[0..n1-1] and src2[0..n2-1] into
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	37 dst[0..n1+n2-1]. In case of ambiguity, put the elements of src1
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	38 before the elements of src2.
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	39 n1 and n2 must be > 0.
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	40 The arrays src1 and src2 must not overlap the dst array, except that
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	41 src1 may be dst[n2..n1+n2-1], or src2 may be dst[n1..n1+n2-1]. */
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	42 static void
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	43 merge (const ELEMENT *src1, size_t n1,
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	44 const ELEMENT *src2, size_t n2,
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	45 ELEMENT *dst)
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	46 {
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	47 for (;;) /* while (n1 > 0 && n2 > 0) */
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	48 {
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	49 if (COMPARE (src1, src2) <= 0)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	50 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	51 dst++ = src1++;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	52 n1--;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	53 if (n1 == 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	54 break;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	55 }
11167 d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	56 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	57 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	58 dst++ = src2++;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	59 n2--;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	60 if (n2 == 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	61 break;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	62 }
11167 d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	63 }
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	64 /* Here n1 == 0 \|\| n2 == 0 but also n1 > 0 \|\| n2 > 0. */
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	65 if (n1 > 0)
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	66 {
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	67 if (dst != src1)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	68 do
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	69 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	70 dst++ = src1++;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	71 n1--;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	72 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	73 while (n1 > 0);
11167 d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	74 }
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	75 else /* n2 > 0 */
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	76 {
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	77 if (dst != src2)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	78 do
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	79 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	80 dst++ = src2++;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	81 n2--;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	82 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	83 while (n2 > 0);
11167 d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	84 }
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	85 }
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	86
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	87 /* Sort src[0..n-1] into dst[0..n-1], using tmp[0..n/2-1] as temporary
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	88 (scratch) storage.
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	89 The arrays src, dst, tmp must not overlap. */
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	90 STATIC void
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	91 merge_sort_fromto (const ELEMENT src, ELEMENT dst, size_t n, ELEMENT *tmp)
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	92 {
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	93 switch (n)
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	94 {
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	95 case 0:
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	96 return;
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	97 case 1:
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	98 /* Nothing to do. */
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	99 dst[0] = src[0];
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	100 return;
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	101 case 2:
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	102 /* Trivial case. */
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	103 if (COMPARE (&src[0], &src[1]) <= 0)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	104 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	105 /* src[0] <= src[1] */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	106 dst[0] = src[0];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	107 dst[1] = src[1];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	108 }
11167 d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	109 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	110 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	111 dst[0] = src[1];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	112 dst[1] = src[0];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	113 }
11167 d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	114 break;
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	115 case 3:
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	116 /* Simple case. */
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	117 if (COMPARE (&src[0], &src[1]) <= 0)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	118 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	119 if (COMPARE (&src[1], &src[2]) <= 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	120 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	121 /* src[0] <= src[1] <= src[2] */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	122 dst[0] = src[0];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	123 dst[1] = src[1];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	124 dst[2] = src[2];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	125 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	126 else if (COMPARE (&src[0], &src[2]) <= 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	127 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	128 /* src[0] <= src[2] < src[1] */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	129 dst[0] = src[0];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	130 dst[1] = src[2];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	131 dst[2] = src[1];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	132 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	133 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	134 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	135 /* src[2] < src[0] <= src[1] */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	136 dst[0] = src[2];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	137 dst[1] = src[0];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	138 dst[2] = src[1];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	139 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	140 }
11167 d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	141 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	142 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	143 if (COMPARE (&src[0], &src[2]) <= 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	144 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	145 /* src[1] < src[0] <= src[2] */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	146 dst[0] = src[1];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	147 dst[1] = src[0];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	148 dst[2] = src[2];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	149 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	150 else if (COMPARE (&src[1], &src[2]) <= 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	151 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	152 /* src[1] <= src[2] < src[0] */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	153 dst[0] = src[1];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	154 dst[1] = src[2];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	155 dst[2] = src[0];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	156 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	157 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	158 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	159 /* src[2] < src[1] < src[0] */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	160 dst[0] = src[2];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	161 dst[1] = src[1];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	162 dst[2] = src[0];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	163 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	164 }
11167 d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	165 break;
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	166 default:
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	167 {
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	168 size_t n1 = n / 2;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	169 size_t n2 = (n + 1) / 2;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	170 /* Note: n1 + n2 = n, n1 <= n2. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	171 /* Sort src[n1..n-1] into dst[n1..n-1], scratching tmp[0..n2/2-1]. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	172 merge_sort_fromto (src + n1, dst + n1, n2, tmp);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	173 /* Sort src[0..n1-1] into tmp[0..n1-1], scratching dst[0..n1-1]. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	174 merge_sort_fromto (src, tmp, n1, dst);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	175 /* Merge the two half results. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	176 merge (tmp, n1, dst + n1, n2, dst);
11167 d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	177 }
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	178 break;
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	179 }
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	180 }
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	181
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	182 /* Sort src[0..n-1], using tmp[0..n-1] as temporary (scratch) storage.
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	183 The arrays src, tmp must not overlap. */
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	184 STATIC void
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	185 merge_sort_inplace (ELEMENT src, size_t n, ELEMENT tmp)
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	186 {
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	187 switch (n)
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	188 {
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	189 case 0:
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	190 case 1:
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	191 /* Nothing to do. */
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	192 return;
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	193 case 2:
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	194 /* Trivial case. */
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	195 if (COMPARE (&src[0], &src[1]) <= 0)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	196 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	197 /* src[0] <= src[1] */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	198 }
11167 d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	199 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	200 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	201 ELEMENT t = src[0];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	202 src[0] = src[1];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	203 src[1] = t;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	204 }
11167 d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	205 break;
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	206 case 3:
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	207 /* Simple case. */
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	208 if (COMPARE (&src[0], &src[1]) <= 0)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	209 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	210 if (COMPARE (&src[1], &src[2]) <= 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	211 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	212 /* src[0] <= src[1] <= src[2] */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	213 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	214 else if (COMPARE (&src[0], &src[2]) <= 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	215 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	216 /* src[0] <= src[2] < src[1] */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	217 ELEMENT t = src[1];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	218 src[1] = src[2];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	219 src[2] = t;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	220 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	221 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	222 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	223 /* src[2] < src[0] <= src[1] */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	224 ELEMENT t = src[0];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	225 src[0] = src[2];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	226 src[2] = src[1];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	227 src[1] = t;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	228 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	229 }
11167 d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	230 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	231 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	232 if (COMPARE (&src[0], &src[2]) <= 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	233 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	234 /* src[1] < src[0] <= src[2] */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	235 ELEMENT t = src[0];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	236 src[0] = src[1];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	237 src[1] = t;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	238 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	239 else if (COMPARE (&src[1], &src[2]) <= 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	240 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	241 /* src[1] <= src[2] < src[0] */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	242 ELEMENT t = src[0];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	243 src[0] = src[1];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	244 src[1] = src[2];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	245 src[2] = t;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	246 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	247 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	248 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	249 /* src[2] < src[1] < src[0] */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	250 ELEMENT t = src[0];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	251 src[0] = src[2];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	252 src[2] = t;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	253 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	254 }
11167 d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	255 break;
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	256 default:
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	257 {
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	258 size_t n1 = n / 2;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	259 size_t n2 = (n + 1) / 2;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	260 /* Note: n1 + n2 = n, n1 <= n2. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	261 /* Sort src[n1..n-1], scratching tmp[0..n2-1]. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	262 merge_sort_inplace (src + n1, n2, tmp);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	263 /* Sort src[0..n1-1] into tmp[0..n1-1], scratching tmp[n1..2n1-1]. /
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	264 merge_sort_fromto (src, tmp, n1, tmp + n1);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	265 /* Merge the two half results. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 11167 diff changeset	266 merge (tmp, n1, src + n1, n2, src);
11167 d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	267 }
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	268 break;
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	269 }
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	270 }
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	271
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	272 #undef ELEMENT
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	273 #undef COMPARE
d11190b43f68 New module 'array-mergesort'. Bruno Haible <bruno@clisp.org> parents: diff changeset	274 #undef STATIC

Mercurial > hg > octave-kai > gnulib-hg

annotate lib/array-mergesort.h @ 17342:c75939cb6254