/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / sources / misc / 4213

< prev

next >

MacOS 8.1

Win98

DOS

browse contents

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 4e 65 77 73 67 72 6f 75 | 70 73 3a 20 63 6f 6d 70 |Newsgrou|ps: comp|
|00000010| 2e 73 6f 75 72 63 65 73 | 2e 6d 69 73 63 0a 50 61 |.sources|.misc.Pa|
|00000020| 74 68 3a 20 73 70 61 72 | 6b 79 21 6b 65 6e 74 0a |th: spar|ky!kent.|
|00000030| 46 72 6f 6d 3a 20 6d 69 | 6b 65 79 40 6f 6e 74 65 |From: mi|key@onte|
|00000040| 6b 2e 63 6f 6d 20 28 4d | 69 6b 65 20 4c 65 65 29 |k.com (M|ike Lee)|
|00000050| 0a 53 75 62 6a 65 63 74 | 3a 20 20 76 33 34 69 30 |.Subject|:  v34i0|
|00000060| 37 33 3a 20 20 66 6c 6f | 67 67 65 72 20 2d 20 53 |73:  flo|gger - S|
|00000070| 6f 72 74 20 46 6c 6f 67 | 67 65 72 20 76 30 2e 30 |ort Flog|ger v0.0|
|00000080| 2c 20 50 61 72 74 30 31 | 2f 30 32 0a 4d 65 73 73 |, Part01|/02.Mess|
|00000090| 61 67 65 2d 49 44 3a 20 | 3c 63 73 6d 2d 76 33 34 |age-ID: |<csm-v34|
|000000a0| 69 30 37 33 3d 66 6c 6f | 67 67 65 72 2e 30 39 31 |i073=flo|gger.091|
|000000b0| 38 31 38 40 73 70 61 72 | 6b 79 2e 49 4d 44 2e 53 |818@spar|ky.IMD.S|
|000000c0| 74 65 72 6c 69 6e 67 2e | 43 4f 4d 3e 0a 46 6f 6c |terling.|COM>.Fol|
|000000d0| 6c 6f 77 75 70 2d 54 6f | 3a 20 63 6f 6d 70 2e 73 |lowup-To|: comp.s|
|000000e0| 6f 75 72 63 65 73 2e 64 | 0a 58 2d 4d 64 34 2d 53 |ources.d|.X-Md4-S|
|000000f0| 69 67 6e 61 74 75 72 65 | 3a 20 66 66 30 61 64 61 |ignature|: ff0ada|
|00000100| 30 34 61 64 37 34 34 39 | 62 36 61 35 61 66 36 30 |04ad7449|b6a5af60|
|00000110| 39 39 31 65 33 63 65 32 | 61 32 0a 53 65 6e 64 65 |991e3ce2|a2.Sende|
|00000120| 72 3a 20 6b 65 6e 74 40 | 73 70 61 72 6b 79 2e 69 |r: kent@|sparky.i|
|00000130| 6d 64 2e 73 74 65 72 6c | 69 6e 67 2e 63 6f 6d 20 |md.sterl|ing.com |
|00000140| 28 4b 65 6e 74 20 4c 61 | 6e 64 66 69 65 6c 64 29 |(Kent La|ndfield)|
|00000150| 0a 4f 72 67 61 6e 69 7a | 61 74 69 6f 6e 3a 20 4f |.Organiz|ation: O|
|00000160| 6e 74 65 6b 20 43 6f 72 | 70 6f 72 61 74 69 6f 6e |ntek Cor|poration|
|00000170| 20 2d 2d 20 4c 61 67 75 | 6e 61 20 48 69 6c 6c 73 | -- Lagu|na Hills|
|00000180| 2c 20 43 61 6c 69 66 6f | 72 6e 69 61 0a 44 61 74 |, Califo|rnia.Dat|
|00000190| 65 3a 20 46 72 69 2c 20 | 31 38 20 44 65 63 20 31 |e: Fri, |18 Dec 1|
|000001a0| 39 39 32 20 31 35 3a 32 | 31 3a 34 36 20 47 4d 54 |992 15:2|1:46 GMT|
|000001b0| 0a 41 70 70 72 6f 76 65 | 64 3a 20 6b 65 6e 74 40 |.Approve|d: kent@|
|000001c0| 73 70 61 72 6b 79 2e 69 | 6d 64 2e 73 74 65 72 6c |sparky.i|md.sterl|
|000001d0| 69 6e 67 2e 63 6f 6d 0a | 4c 69 6e 65 73 3a 20 31 |ing.com.|Lines: 1|
|000001e0| 37 38 31 0a 0a 53 75 62 | 6d 69 74 74 65 64 2d 62 |781..Sub|mitted-b|
|000001f0| 79 3a 20 6d 69 6b 65 79 | 40 6f 6e 74 65 6b 2e 63 |y: mikey|@ontek.c|
|00000200| 6f 6d 20 28 4d 69 6b 65 | 20 4c 65 65 29 0a 50 6f |om (Mike| Lee).Po|
|00000210| 73 74 69 6e 67 2d 6e 75 | 6d 62 65 72 3a 20 56 6f |sting-nu|mber: Vo|
|00000220| 6c 75 6d 65 20 33 34 2c | 20 49 73 73 75 65 20 37 |lume 34,| Issue 7|
|00000230| 33 0a 41 72 63 68 69 76 | 65 2d 6e 61 6d 65 3a 20 |3.Archiv|e-name: |
|00000240| 66 6c 6f 67 67 65 72 2f | 70 61 72 74 30 31 0a 45 |flogger/|part01.E|
|00000250| 6e 76 69 72 6f 6e 6d 65 | 6e 74 3a 20 55 4e 49 58 |nvironme|nt: UNIX|
|00000260| 0a 0a 54 68 69 73 20 69 | 73 20 61 20 73 6d 61 6c |..This i|s a smal|
|00000270| 6c 20 63 6f 6c 6c 65 63 | 74 69 6f 6e 20 6f 66 20 |l collec|tion of |
|00000280| 73 6f 6d 65 20 6f 66 20 | 74 68 65 20 6d 6f 72 65 |some of |the more|
|00000290| 20 70 6f 70 75 6c 61 72 | 20 73 6f 72 74 0a 61 6c | popular| sort.al|
|000002a0| 67 6f 72 69 74 68 6d 73 | 2c 20 69 6e 63 6c 75 64 |gorithms|, includ|
|000002b0| 69 6e 67 3a 0a 0a 20 20 | 20 20 20 20 62 75 62 62 |ing:..  |    bubb|
|000002c0| 6c 65 20 73 6f 72 74 20 | 2d 2d 20 61 6e 79 20 31 |le sort |-- any 1|
|000002d0| 73 74 20 73 65 6d 65 73 | 74 65 72 20 63 6f 75 72 |st semes|ter cour|
|000002e0| 73 65 20 69 6e 20 43 53 | 0a 20 20 20 20 20 20 68 |se in CS|.      h|
|000002f0| 65 61 70 20 73 6f 72 74 | 20 2d 2d 20 63 6f 6e 74 |eap sort| -- cont|
|00000300| 72 69 62 75 74 65 64 20 | 62 79 20 64 65 72 20 4d |ributed |by der M|
|00000310| 6f 75 73 65 0a 20 20 20 | 20 20 20 69 6e 73 65 72 |ouse.   |   inser|
|00000320| 74 69 6f 6e 20 73 6f 72 | 74 20 2d 2d 20 61 6e 79 |tion sor|t -- any|
|00000330| 20 31 73 74 20 73 65 6d | 65 73 74 65 72 20 63 6f | 1st sem|ester co|
|00000340| 75 72 73 65 20 69 6e 20 | 43 53 0a 20 20 20 20 20 |urse in |CS.     |
|00000350| 20 6d 65 72 67 65 20 73 | 6f 72 74 20 2d 2d 20 72 | merge s|ort -- r|
|00000360| 6f 75 67 68 6c 79 20 70 | 61 74 74 65 72 6e 65 64 |oughly p|atterned|
|00000370| 20 61 66 74 65 72 20 4b | 6e 75 74 68 20 56 6f 6c | after K|nuth Vol|
|00000380| 2e 20 33 0a 20 20 20 20 | 20 20 71 75 69 63 6b 20 |. 3.    |  quick |
|00000390| 73 6f 72 74 20 2d 2d 20 | 43 2e 41 2e 52 2e 20 48 |sort -- |C.A.R. H|
|000003a0| 6f 61 72 65 27 73 20 61 | 73 20 67 69 76 65 6e 20 |oare's a|s given |
|000003b0| 69 6e 20 4b 26 52 20 32 | 20 70 67 20 38 37 0a 20 |in K&R 2| pg 87. |
|000003c0| 20 20 20 20 20 73 68 65 | 6c 6c 20 73 6f 72 74 20 |     she|ll sort |
|000003d0| 2d 2d 20 44 2e 4c 2e 20 | 53 68 65 6c 6c 20 61 73 |-- D.L. |Shell as|
|000003e0| 20 67 69 76 65 6e 20 69 | 6e 20 4b 26 52 20 32 20 | given i|n K&R 2 |
|000003f0| 70 67 20 36 32 0a 20 20 | 20 20 20 20 62 6f 67 6f |pg 62.  |    bogo|
|00000400| 20 73 6f 72 74 20 2d 2d | 20 77 6f 72 73 74 2d 63 | sort --| worst-c|
|00000410| 61 73 65 20 73 6f 72 74 | 20 62 79 20 52 69 63 68 |ase sort| by Rich|
|00000420| 61 72 64 20 4b 72 65 68 | 62 69 65 6c 0a 0a 41 20 |ard Kreh|biel..A |
|00000430| 73 6c 69 67 68 74 6c 79 | 20 77 65 69 72 64 20 74 |slightly| weird t|
|00000440| 65 73 74 20 72 6f 75 74 | 69 6e 65 20 69 73 20 70 |est rout|ine is p|
|00000450| 72 6f 76 69 64 65 64 20 | 77 68 69 63 68 20 63 61 |rovided |which ca|
|00000460| 6c 63 75 6c 61 74 65 73 | 20 73 6f 6d 65 0a 70 65 |lculates| some.pe|
|00000470| 72 66 6f 72 6d 61 6e 63 | 65 20 6d 65 61 73 75 72 |rformanc|e measur|
|00000480| 65 6d 65 6e 74 73 20 6f | 6e 20 74 68 65 20 61 62 |ements o|n the ab|
|00000490| 6f 76 65 20 61 6c 67 6f | 72 69 74 68 6d 73 20 61 |ove algo|rithms a|
|000004a0| 6e 64 20 61 6c 73 6f 20 | 6f 6e 20 74 68 65 0a 71 |nd also |on the.q|
|000004b0| 73 6f 72 74 28 29 20 66 | 75 6e 63 74 69 6f 6e 20 |sort() f|unction |
|000004c0| 70 72 6f 76 69 64 65 64 | 20 77 69 74 68 20 79 6f |provided| with yo|
|000004d0| 75 72 20 73 79 73 74 65 | 6d 2c 20 61 73 20 77 65 |ur syste|m, as we|
|000004e0| 6c 6c 20 61 73 20 76 65 | 72 69 66 79 69 6e 67 20 |ll as ve|rifying |
|000004f0| 74 68 61 74 0a 74 68 65 | 20 73 6f 72 74 20 61 63 |that.the| sort ac|
|00000500| 74 75 61 6c 6c 79 20 77 | 6f 72 6b 65 64 20 61 6e |tually w|orked an|
|00000510| 64 20 74 68 61 74 20 69 | 74 20 64 69 64 6e 27 74 |d that i|t didn't|
|00000520| 20 6d 6f 64 69 66 79 20 | 61 6e 79 74 68 69 6e 67 | modify |anything|
|00000530| 20 69 6d 6d 65 64 69 61 | 74 65 6c 79 0a 61 62 6f | immedia|tely.abo|
|00000540| 76 65 20 6f 72 20 62 65 | 6c 6f 77 20 74 68 65 20 |ve or be|low the |
|00000550| 61 72 72 61 79 2c 20 74 | 68 61 74 20 69 74 20 64 |array, t|hat it d|
|00000560| 6f 65 73 6e 27 74 20 6c | 65 61 6b 20 6d 65 6d 6f |oesn't l|eak memo|
|00000570| 72 79 2c 20 61 6e 64 20 | 77 68 65 74 68 65 72 0a |ry, and |whether.|
|00000580| 6f 72 20 6e 6f 74 20 69 | 74 27 73 20 73 74 61 62 |or not i|t's stab|
|00000590| 6c 65 2e 20 20 54 68 65 | 73 65 20 74 65 73 74 73 |le.  The|se tests|
|000005a0| 20 61 72 65 20 63 61 72 | 72 69 65 64 20 6f 75 74 | are car|ried out|
|000005b0| 20 69 6e 20 61 20 76 61 | 72 69 65 74 79 20 6f 66 | in a va|riety of|
|000005c0| 0a 73 69 74 75 61 74 69 | 6f 6e 73 20 64 65 73 69 |.situati|ons desi|
|000005d0| 67 6e 65 64 20 74 6f 20 | 68 69 67 68 6c 69 67 68 |gned to |highligh|
|000005e0| 74 20 77 6f 72 73 74 2d | 63 61 73 65 20 62 65 68 |t worst-|case beh|
|000005f0| 61 76 69 6f 72 2e 0a 0a | 54 68 65 73 65 20 69 6d |avior...|These im|
|00000600| 70 6c 65 6d 65 6e 74 61 | 74 69 6f 6e 73 20 6f 66 |plementa|tions of|
|00000610| 20 74 68 65 20 73 6f 72 | 74 20 66 75 6e 63 74 69 | the sor|t functi|
|00000620| 6f 6e 73 20 61 72 65 20 | 61 6c 6c 20 63 6f 6d 70 |ons are |all comp|
|00000630| 61 74 69 62 6c 65 20 77 | 69 74 68 0a 71 73 6f 72 |atible w|ith.qsor|
|00000640| 74 28 29 27 73 20 70 61 | 72 61 6d 65 74 65 72 20 |t()'s pa|rameter |
|00000650| 6c 69 73 74 2c 20 73 6f | 20 69 66 20 79 6f 75 20 |list, so| if you |
|00000660| 74 68 69 6e 6b 20 79 6f | 75 72 20 61 70 70 6c 69 |think yo|ur appli|
|00000670| 63 61 74 69 6f 6e 20 73 | 70 65 6e 64 73 20 74 6f |cation s|pends to|
|00000680| 6f 0a 6d 75 63 68 20 74 | 69 6d 65 20 73 6f 72 74 |o.much t|ime sort|
|00000690| 69 6e 67 2c 20 79 6f 75 | 20 63 61 6e 20 6a 75 73 |ing, you| can jus|
|000006a0| 74 20 73 2f 71 73 6f 72 | 74 2f 6d 65 72 67 65 5f |t s/qsor|t/merge_|
|000006b0| 73 6f 72 74 2f 20 61 6e | 64 20 6c 69 6e 6b 20 69 |sort/ an|d link i|
|000006c0| 6e 20 74 68 65 0a 73 6f | 72 74 20 6c 69 62 72 61 |n the.so|rt libra|
|000006d0| 72 79 20 61 6e 64 20 67 | 69 76 65 20 69 74 20 61 |ry and g|ive it a|
|000006e0| 20 74 72 79 2e 20 20 49 | 66 20 79 6f 75 20 74 68 | try.  I|f you th|
|000006f0| 69 6e 6b 20 69 74 20 64 | 6f 65 73 6e 27 74 20 73 |ink it d|oesn't s|
|00000700| 70 65 6e 64 20 2a 65 6e | 6f 75 67 68 2a 0a 74 69 |pend *en|ough*.ti|
|00000710| 6d 65 20 73 6f 72 74 69 | 6e 67 2c 20 74 72 79 20 |me sorti|ng, try |
|00000720| 62 75 62 62 6c 65 5f 73 | 6f 72 74 20 69 6e 73 74 |bubble_s|ort inst|
|00000730| 65 61 64 2e 0a 0a 54 68 | 65 20 68 65 61 70 73 6f |ead...Th|e heapso|
|00000740| 72 74 20 77 61 73 20 63 | 6f 6e 74 72 69 62 75 74 |rt was c|ontribut|
|00000750| 65 64 20 62 79 20 6d 6f | 75 73 65 40 6c 61 72 72 |ed by mo|use@larr|
|00000760| 79 2e 6d 63 72 63 69 6d | 2e 6d 63 67 69 6c 6c 2e |y.mcrcim|.mcgill.|
|00000770| 65 64 75 0a 61 6b 61 20 | 22 64 65 72 20 4d 6f 75 |edu.aka |"der Mou|
|00000780| 73 65 22 2e 0a 2d 2d 2d | 2d 2d 2d 0a 23 21 20 2f |se"..---|---.#! /|
|00000790| 62 69 6e 2f 73 68 0a 23 | 20 54 68 69 73 20 69 73 |bin/sh.#| This is|
|000007a0| 20 61 20 73 68 65 6c 6c | 20 61 72 63 68 69 76 65 | a shell| archive|
|000007b0| 2e 20 20 52 65 6d 6f 76 | 65 20 61 6e 79 74 68 69 |.  Remov|e anythi|
|000007c0| 6e 67 20 62 65 66 6f 72 | 65 20 74 68 69 73 20 6c |ng befor|e this l|
|000007d0| 69 6e 65 2c 20 74 68 65 | 6e 20 66 65 65 64 20 69 |ine, the|n feed i|
|000007e0| 74 0a 23 20 69 6e 74 6f | 20 61 20 73 68 65 6c 6c |t.# into| a shell|
|000007f0| 20 76 69 61 20 22 73 68 | 20 66 69 6c 65 22 20 6f | via "sh| file" o|
|00000800| 72 20 73 69 6d 69 6c 61 | 72 2e 20 20 54 6f 20 6f |r simila|r.  To o|
|00000810| 76 65 72 77 72 69 74 65 | 20 65 78 69 73 74 69 6e |verwrite| existin|
|00000820| 67 20 66 69 6c 65 73 2c | 0a 23 20 74 79 70 65 20 |g files,|.# type |
|00000830| 22 73 68 20 66 69 6c 65 | 20 2d 63 22 2e 0a 23 20 |"sh file| -c"..# |
|00000840| 43 6f 6e 74 65 6e 74 73 | 3a 20 20 52 45 41 44 4d |Contents|:  READM|
|00000850| 45 20 4f 50 54 49 4d 49 | 5a 49 4e 47 20 54 4f 44 |E OPTIMI|ZING TOD|
|00000860| 4f 20 66 6c 6f 67 67 65 | 72 2e 63 20 68 65 61 70 |O flogge|r.c heap|
|00000870| 5f 73 6f 72 74 2e 63 20 | 6d 65 72 67 65 5f 73 6f |_sort.c |merge_so|
|00000880| 72 74 2e 63 0a 23 20 20 | 20 71 75 69 63 6b 5f 73 |rt.c.#  | quick_s|
|00000890| 6f 72 74 2e 63 0a 23 20 | 57 72 61 70 70 65 64 20 |ort.c.# |Wrapped |
|000008a0| 62 79 20 6b 65 6e 74 40 | 73 70 61 72 6b 79 20 6f |by kent@|sparky o|
|000008b0| 6e 20 54 68 75 20 44 65 | 63 20 31 37 20 31 33 3a |n Thu De|c 17 13:|
|000008c0| 35 30 3a 33 34 20 31 39 | 39 32 0a 50 41 54 48 3d |50:34 19|92.PATH=|
|000008d0| 2f 62 69 6e 3a 2f 75 73 | 72 2f 62 69 6e 3a 2f 75 |/bin:/us|r/bin:/u|
|000008e0| 73 72 2f 75 63 62 3a 2f | 75 73 72 2f 6c 6f 63 61 |sr/ucb:/|usr/loca|
|000008f0| 6c 2f 62 69 6e 3a 2f 75 | 73 72 2f 6c 62 69 6e 20 |l/bin:/u|sr/lbin |
|00000900| 3b 20 65 78 70 6f 72 74 | 20 50 41 54 48 0a 65 63 |; export| PATH.ec|
|00000910| 68 6f 20 49 66 20 74 68 | 69 73 20 61 72 63 68 69 |ho If th|is archi|
|00000920| 76 65 20 69 73 20 63 6f | 6d 70 6c 65 74 65 2c 20 |ve is co|mplete, |
|00000930| 79 6f 75 20 77 69 6c 6c | 20 73 65 65 20 74 68 65 |you will| see the|
|00000940| 20 66 6f 6c 6c 6f 77 69 | 6e 67 20 6d 65 73 73 61 | followi|ng messa|
|00000950| 67 65 3a 0a 65 63 68 6f | 20 27 20 20 20 20 20 20 |ge:.echo| '      |
|00000960| 20 20 20 20 22 73 68 61 | 72 3a 20 45 6e 64 20 6f |    "sha|r: End o|
|00000970| 66 20 61 72 63 68 69 76 | 65 20 31 20 28 6f 66 20 |f archiv|e 1 (of |
|00000980| 32 29 2e 22 27 0a 69 66 | 20 74 65 73 74 20 2d 66 |2)."'.if| test -f|
|00000990| 20 27 52 45 41 44 4d 45 | 27 20 2d 61 20 22 24 7b | 'README|' -a "${|
|000009a0| 31 7d 22 20 21 3d 20 22 | 2d 63 22 20 3b 20 74 68 |1}" != "|-c" ; th|
|000009b0| 65 6e 20 0a 20 20 65 63 | 68 6f 20 73 68 61 72 3a |en .  ec|ho shar:|
|000009c0| 20 57 69 6c 6c 20 6e 6f | 74 20 63 6c 6f 62 62 65 | Will no|t clobbe|
|000009d0| 72 20 65 78 69 73 74 69 | 6e 67 20 66 69 6c 65 20 |r existi|ng file |
|000009e0| 5c 22 27 52 45 41 44 4d | 45 27 5c 22 0a 65 6c 73 |\"'READM|E'\".els|
|000009f0| 65 0a 20 20 65 63 68 6f | 20 73 68 61 72 3a 20 45 |e.  echo| shar: E|
|00000a00| 78 74 72 61 63 74 69 6e | 67 20 5c 22 27 52 45 41 |xtractin|g \"'REA|
|00000a10| 44 4d 45 27 5c 22 20 5c | 28 37 39 39 33 20 63 68 |DME'\" \|(7993 ch|
|00000a20| 61 72 61 63 74 65 72 73 | 5c 29 0a 20 20 73 65 64 |aracters|\).  sed|
|00000a30| 20 22 73 2f 5e 58 2f 2f | 22 20 3e 27 52 45 41 44 | "s/^X//|" >'READ|
|00000a40| 4d 45 27 20 3c 3c 27 45 | 4e 44 5f 4f 46 5f 46 49 |ME' <<'E|ND_OF_FI|
|00000a50| 4c 45 27 0a 58 0a 58 56 | 45 52 53 49 4f 4e 0a 58 |LE'.X.XV|ERSION.X|
|00000a60| 0a 58 20 20 20 20 54 68 | 69 73 20 69 73 20 76 65 |.X    Th|is is ve|
|00000a70| 72 73 69 6f 6e 20 30 20 | 6f 66 20 74 68 65 20 74 |rsion 0 |of the t|
|00000a80| 68 65 20 53 6f 72 74 20 | 46 6c 6f 67 67 65 72 2e |he Sort |Flogger.|
|00000a90| 0a 58 0a 58 4f 56 45 52 | 56 49 45 57 0a 58 0a 58 |.X.XOVER|VIEW.X.X|
|00000aa0| 20 20 20 20 54 68 69 73 | 20 69 73 20 61 20 73 6d |    This| is a sm|
|00000ab0| 61 6c 6c 20 63 6f 6c 6c | 65 63 74 69 6f 6e 20 6f |all coll|ection o|
|00000ac0| 66 20 73 6f 6d 65 20 6f | 66 20 74 68 65 20 6d 6f |f some o|f the mo|
|00000ad0| 72 65 20 70 6f 70 75 6c | 61 72 20 73 6f 72 74 0a |re popul|ar sort.|
|00000ae0| 58 61 6c 67 6f 72 69 74 | 68 6d 73 2c 20 69 6e 63 |Xalgorit|hms, inc|
|00000af0| 6c 75 64 69 6e 67 3a 0a | 58 0a 58 20 20 20 20 20 |luding:.|X.X     |
|00000b00| 20 62 75 62 62 6c 65 20 | 73 6f 72 74 20 2d 2d 20 | bubble |sort -- |
|00000b10| 61 6e 79 20 31 73 74 20 | 73 65 6d 65 73 74 65 72 |any 1st |semester|
|00000b20| 20 63 6f 75 72 73 65 20 | 69 6e 20 43 53 0a 58 20 | course |in CS.X |
|00000b30| 20 20 20 20 20 68 65 61 | 70 20 73 6f 72 74 20 2d |     hea|p sort -|
|00000b40| 2d 20 63 6f 6e 74 72 69 | 62 75 74 65 64 20 62 79 |- contri|buted by|
|00000b50| 20 64 65 72 20 4d 6f 75 | 73 65 0a 58 20 20 20 20 | der Mou|se.X    |
|00000b60| 20 20 69 6e 73 65 72 74 | 69 6f 6e 20 73 6f 72 74 |  insert|ion sort|
|00000b70| 20 2d 2d 20 61 6e 79 20 | 31 73 74 20 73 65 6d 65 | -- any |1st seme|
|00000b80| 73 74 65 72 20 63 6f 75 | 72 73 65 20 69 6e 20 43 |ster cou|rse in C|
|00000b90| 53 0a 58 20 20 20 20 20 | 20 6d 65 72 67 65 20 73 |S.X     | merge s|
|00000ba0| 6f 72 74 20 2d 2d 20 72 | 6f 75 67 68 6c 79 20 70 |ort -- r|oughly p|
|00000bb0| 61 74 74 65 72 6e 65 64 | 20 61 66 74 65 72 20 4b |atterned| after K|
|00000bc0| 6e 75 74 68 20 56 6f 6c | 2e 20 33 0a 58 20 20 20 |nuth Vol|. 3.X   |
|00000bd0| 20 20 20 71 75 69 63 6b | 20 73 6f 72 74 20 2d 2d |   quick| sort --|
|00000be0| 20 43 2e 41 2e 52 2e 20 | 48 6f 61 72 65 27 73 20 | C.A.R. |Hoare's |
|00000bf0| 61 73 20 67 69 76 65 6e | 20 69 6e 20 4b 26 52 20 |as given| in K&R |
|00000c00| 32 20 70 67 20 38 37 0a | 58 20 20 20 20 20 20 73 |2 pg 87.|X      s|
|00000c10| 68 65 6c 6c 20 73 6f 72 | 74 20 2d 2d 20 44 2e 4c |hell sor|t -- D.L|
|00000c20| 2e 20 53 68 65 6c 6c 20 | 61 73 20 67 69 76 65 6e |. Shell |as given|
|00000c30| 20 69 6e 20 4b 26 52 20 | 32 20 70 67 20 36 32 0a | in K&R |2 pg 62.|
|00000c40| 58 20 20 20 20 20 20 62 | 6f 67 6f 20 73 6f 72 74 |X      b|ogo sort|
|00000c50| 20 2d 2d 20 77 6f 72 73 | 74 2d 63 61 73 65 20 73 | -- wors|t-case s|
|00000c60| 6f 72 74 20 62 79 20 52 | 69 63 68 61 72 64 20 4b |ort by R|ichard K|
|00000c70| 72 65 68 62 69 65 6c 0a | 58 0a 58 20 20 20 20 41 |rehbiel.|X.X    A|
|00000c80| 20 73 6c 69 67 68 74 6c | 79 20 77 65 69 72 64 20 | slightl|y weird |
|00000c90| 74 65 73 74 20 72 6f 75 | 74 69 6e 65 20 69 73 20 |test rou|tine is |
|00000ca0| 70 72 6f 76 69 64 65 64 | 20 77 68 69 63 68 20 63 |provided| which c|
|00000cb0| 61 6c 63 75 6c 61 74 65 | 73 20 73 6f 6d 65 0a 58 |alculate|s some.X|
|00000cc0| 70 65 72 66 6f 72 6d 61 | 6e 63 65 20 6d 65 61 73 |performa|nce meas|
|00000cd0| 75 72 65 6d 65 6e 74 73 | 20 6f 6e 20 74 68 65 20 |urements| on the |
|00000ce0| 61 62 6f 76 65 20 61 6c | 67 6f 72 69 74 68 6d 73 |above al|gorithms|
|00000cf0| 20 61 6e 64 20 61 6c 73 | 6f 20 6f 6e 20 74 68 65 | and als|o on the|
|00000d00| 0a 58 71 73 6f 72 74 28 | 29 20 66 75 6e 63 74 69 |.Xqsort(|) functi|
|00000d10| 6f 6e 20 70 72 6f 76 69 | 64 65 64 20 77 69 74 68 |on provi|ded with|
|00000d20| 20 79 6f 75 72 20 73 79 | 73 74 65 6d 2c 20 61 73 | your sy|stem, as|
|00000d30| 20 77 65 6c 6c 20 61 73 | 20 76 65 72 69 66 79 69 | well as| verifyi|
|00000d40| 6e 67 20 74 68 61 74 0a | 58 74 68 65 20 73 6f 72 |ng that.|Xthe sor|
|00000d50| 74 20 61 63 74 75 61 6c | 6c 79 20 77 6f 72 6b 65 |t actual|ly worke|
|00000d60| 64 20 61 6e 64 20 74 68 | 61 74 20 69 74 20 64 69 |d and th|at it di|
|00000d70| 64 6e 27 74 20 6d 6f 64 | 69 66 79 20 61 6e 79 74 |dn't mod|ify anyt|
|00000d80| 68 69 6e 67 20 69 6d 6d | 65 64 69 61 74 65 6c 79 |hing imm|ediately|
|00000d90| 0a 58 61 62 6f 76 65 20 | 6f 72 20 62 65 6c 6f 77 |.Xabove |or below|
|00000da0| 20 74 68 65 20 61 72 72 | 61 79 2c 20 74 68 61 74 | the arr|ay, that|
|00000db0| 20 69 74 20 64 6f 65 73 | 6e 27 74 20 6c 65 61 6b | it does|n't leak|
|00000dc0| 20 6d 65 6d 6f 72 79 2c | 20 61 6e 64 20 77 68 65 | memory,| and whe|
|00000dd0| 74 68 65 72 0a 58 6f 72 | 20 6e 6f 74 20 69 74 27 |ther.Xor| not it'|
|00000de0| 73 20 73 74 61 62 6c 65 | 2e 20 20 54 68 65 73 65 |s stable|.  These|
|00000df0| 20 74 65 73 74 73 20 61 | 72 65 20 63 61 72 72 69 | tests a|re carri|
|00000e00| 65 64 20 6f 75 74 20 69 | 6e 20 61 20 76 61 72 69 |ed out i|n a vari|
|00000e10| 65 74 79 20 6f 66 0a 58 | 73 69 74 75 61 74 69 6f |ety of.X|situatio|
|00000e20| 6e 73 20 64 65 73 69 67 | 6e 65 64 20 74 6f 20 68 |ns desig|ned to h|
|00000e30| 69 67 68 6c 69 67 68 74 | 20 77 6f 72 73 74 2d 63 |ighlight| worst-c|
|00000e40| 61 73 65 20 62 65 68 61 | 76 69 6f 72 2e 0a 58 0a |ase beha|vior..X.|
|00000e50| 58 20 20 20 20 54 68 65 | 73 65 20 69 6d 70 6c 65 |X    The|se imple|
|00000e60| 6d 65 6e 74 61 74 69 6f | 6e 73 20 6f 66 20 74 68 |mentatio|ns of th|
|00000e70| 65 20 73 6f 72 74 20 66 | 75 6e 63 74 69 6f 6e 73 |e sort f|unctions|
|00000e80| 20 61 72 65 20 61 6c 6c | 20 63 6f 6d 70 61 74 69 | are all| compati|
|00000e90| 62 6c 65 20 77 69 74 68 | 0a 58 71 73 6f 72 74 28 |ble with|.Xqsort(|
|00000ea0| 29 27 73 20 70 61 72 61 | 6d 65 74 65 72 20 6c 69 |)'s para|meter li|
|00000eb0| 73 74 2c 20 73 6f 20 69 | 66 20 79 6f 75 20 74 68 |st, so i|f you th|
|00000ec0| 69 6e 6b 20 79 6f 75 72 | 20 61 70 70 6c 69 63 61 |ink your| applica|
|00000ed0| 74 69 6f 6e 20 73 70 65 | 6e 64 73 20 74 6f 6f 0a |tion spe|nds too.|
|00000ee0| 58 6d 75 63 68 20 74 69 | 6d 65 20 73 6f 72 74 69 |Xmuch ti|me sorti|
|00000ef0| 6e 67 2c 20 79 6f 75 20 | 63 61 6e 20 6a 75 73 74 |ng, you |can just|
|00000f00| 20 73 2f 71 73 6f 72 74 | 2f 6d 65 72 67 65 5f 73 | s/qsort|/merge_s|
|00000f10| 6f 72 74 2f 20 61 6e 64 | 20 6c 69 6e 6b 20 69 6e |ort/ and| link in|
|00000f20| 20 74 68 65 0a 58 73 6f | 72 74 20 6c 69 62 72 61 | the.Xso|rt libra|
|00000f30| 72 79 20 61 6e 64 20 67 | 69 76 65 20 69 74 20 61 |ry and g|ive it a|
|00000f40| 20 74 72 79 2e 20 20 49 | 66 20 79 6f 75 20 74 68 | try.  I|f you th|
|00000f50| 69 6e 6b 20 69 74 20 64 | 6f 65 73 6e 27 74 20 73 |ink it d|oesn't s|
|00000f60| 70 65 6e 64 20 2a 65 6e | 6f 75 67 68 2a 0a 58 74 |pend *en|ough*.Xt|
|00000f70| 69 6d 65 20 73 6f 72 74 | 69 6e 67 2c 20 74 72 79 |ime sort|ing, try|
|00000f80| 20 62 75 62 62 6c 65 5f | 73 6f 72 74 20 69 6e 73 | bubble_|sort ins|
|00000f90| 74 65 61 64 2e 0a 58 0a | 58 20 20 20 20 54 68 65 |tead..X.|X    The|
|00000fa0| 20 6d 65 72 67 65 20 73 | 6f 72 74 20 64 65 63 6c | merge s|ort decl|
|00000fb0| 61 72 65 73 20 61 20 67 | 6c 6f 62 61 6c 20 69 6e |ares a g|lobal in|
|00000fc0| 74 20 63 61 6c 6c 65 64 | 20 5f 6d 61 79 62 65 5f |t called| _maybe_|
|00000fd0| 73 6f 72 74 65 64 20 77 | 68 69 63 68 0a 58 74 65 |sorted w|hich.Xte|
|00000fe0| 6c 6c 73 20 6d 65 72 67 | 65 20 73 6f 72 74 20 74 |lls merg|e sort t|
|00000ff0| 68 61 74 20 74 68 65 20 | 64 61 74 61 20 69 6e 20 |hat the |data in |
|00001000| 74 68 65 20 61 72 72 61 | 79 20 6d 61 79 20 61 6c |the arra|y may al|
|00001010| 72 65 61 64 79 20 62 65 | 20 6d 6f 73 74 6c 79 20 |ready be| mostly |
|00001020| 69 6e 0a 58 6f 72 64 65 | 72 2e 20 20 49 74 20 69 |in.Xorde|r.  It i|
|00001030| 73 20 61 64 76 69 73 6f | 72 79 2d 2d 74 68 65 20 |s adviso|ry--the |
|00001040| 61 6c 67 6f 72 69 74 68 | 6d 20 77 69 6c 6c 20 70 |algorith|m will p|
|00001050| 72 6f 64 75 63 65 20 74 | 68 65 20 63 6f 72 72 65 |roduce t|he corre|
|00001060| 63 74 20 72 65 73 75 6c | 74 73 0a 58 72 65 67 61 |ct resul|ts.Xrega|
|00001070| 72 64 6c 65 73 73 20 6f | 66 20 5f 6d 61 79 62 65 |rdless o|f _maybe|
|00001080| 5f 73 6f 72 74 65 64 27 | 73 20 76 61 6c 75 65 3b |_sorted'|s value;|
|00001090| 20 68 6f 77 65 76 65 72 | 20 74 68 65 20 65 78 65 | however| the exe|
|000010a0| 63 75 74 69 6f 6e 20 74 | 69 6d 65 20 66 6f 72 0a |cution t|ime for.|
|000010b0| 58 6d 65 72 67 65 5f 73 | 6f 72 74 20 77 69 6c 6c |Xmerge_s|ort will|
|000010c0| 20 62 65 20 71 75 69 74 | 65 20 61 20 62 69 74 20 | be quit|e a bit |
|000010d0| 6c 65 73 73 20 69 66 20 | 74 68 69 73 20 69 73 20 |less if |this is |
|000010e0| 73 65 74 20 61 6e 64 20 | 74 68 65 20 61 72 72 61 |set and |the arra|
|000010f0| 79 20 69 73 0a 58 61 6c | 72 65 61 64 79 20 6d 6f |y is.Xal|ready mo|
|00001100| 73 74 6c 79 20 73 6f 72 | 74 65 64 2e 20 20 49 66 |stly sor|ted.  If|
|00001110| 20 74 68 65 20 61 72 72 | 61 79 20 69 73 6e 27 74 | the arr|ay isn't|
|00001120| 20 73 6f 72 74 65 64 20 | 61 74 20 61 6c 6c 2c 20 | sorted |at all, |
|00001130| 74 68 69 73 20 6f 70 74 | 69 6f 6e 0a 58 65 78 74 |this opt|ion.Xext|
|00001140| 72 61 63 74 73 20 61 62 | 6f 75 74 20 32 25 20 73 |racts ab|out 2% s|
|00001150| 70 65 65 64 20 70 65 6e | 61 6c 74 79 2e 0a 58 0a |peed pen|alty..X.|
|00001160| 58 20 20 20 20 54 68 65 | 20 68 65 61 70 73 6f 72 |X    The| heapsor|
|00001170| 74 20 77 61 73 20 63 6f | 6e 74 72 69 62 75 74 65 |t was co|ntribute|
|00001180| 64 20 62 79 20 6d 6f 75 | 73 65 40 6c 61 72 72 79 |d by mou|se@larry|
|00001190| 2e 6d 63 72 63 69 6d 2e | 6d 63 67 69 6c 6c 2e 65 |.mcrcim.|mcgill.e|
|000011a0| 64 75 0a 58 61 6b 61 20 | 22 64 65 72 20 4d 6f 75 |du.Xaka |"der Mou|
|000011b0| 73 65 22 2e 0a 58 0a 58 | 20 20 20 20 54 68 65 20 |se"..X.X|    The |
|000011c0| 6d 65 72 67 65 5f 73 6f | 72 74 28 29 20 66 75 6e |merge_so|rt() fun|
|000011d0| 63 74 69 6f 6e 20 69 73 | 20 74 68 65 20 6f 6e 6c |ction is| the onl|
|000011e0| 79 20 6f 6e 65 20 49 27 | 76 65 20 74 61 6b 65 6e |y one I'|ve taken|
|000011f0| 20 61 6e 79 20 74 72 6f | 75 62 6c 65 20 74 6f 0a | any tro|uble to.|
|00001200| 58 6f 70 74 69 6d 69 7a | 65 2e 0a 58 0a 58 49 4e |Xoptimiz|e..X.XIN|
|00001210| 53 54 41 4c 4c 41 54 49 | 4f 4e 0a 58 0a 58 20 20 |STALLATI|ON.X.X  |
|00001220| 20 20 53 65 65 20 74 68 | 65 20 49 4e 53 54 41 4c |  See th|e INSTAL|
|00001230| 4c 41 54 49 4f 4e 20 64 | 6f 63 75 6d 65 6e 74 20 |LATION d|ocument |
|00001240| 77 68 69 63 68 20 73 68 | 6f 75 6c 64 20 62 65 20 |which sh|ould be |
|00001250| 6e 65 61 72 62 79 2e 0a | 58 0a 58 55 53 41 47 45 |nearby..|X.XUSAGE|
|00001260| 0a 58 0a 58 20 20 20 20 | 4a 75 73 74 20 74 79 70 |.X.X    |Just typ|
|00001270| 65 20 22 66 6c 6f 67 67 | 65 72 22 20 6f 72 20 22 |e "flogg|er" or "|
|00001280| 66 6c 6f 67 67 65 72 20 | 3c 6e 75 6d 62 65 72 3e |flogger |<number>|
|00001290| 22 20 61 6e 64 20 77 61 | 74 63 68 20 77 68 61 74 |" and wa|tch what|
|000012a0| 20 68 61 70 70 65 6e 73 | 2e 0a 58 0a 58 44 45 53 | happens|..X.XDES|
|000012b0| 43 52 49 50 54 49 4f 4e | 20 4f 46 20 4f 55 54 50 |CRIPTION| OF OUTP|
|000012c0| 55 54 0a 58 0a 58 20 20 | 20 20 49 74 20 73 65 65 |UT.X.X  |  It see|
|000012d0| 6d 73 20 6c 69 6b 65 20 | 69 74 20 64 6f 65 73 6e |ms like |it doesn|
|000012e0| 27 74 20 72 65 61 6c 6c | 79 20 64 6f 20 61 6e 79 |'t reall|y do any|
|000012f0| 74 68 69 6e 67 20 62 75 | 74 20 73 70 69 74 20 6f |thing bu|t spit o|
|00001300| 75 74 20 6e 75 6d 62 65 | 72 73 2c 0a 58 61 6e 64 |ut numbe|rs,.Xand|
|00001310| 20 72 61 74 68 65 72 20 | 73 6c 6f 77 6c 79 20 61 | rather |slowly a|
|00001320| 74 20 74 68 61 74 2e 20 | 20 54 68 65 20 76 65 72 |t that. | The ver|
|00001330| 73 69 6f 6e 20 61 6e 64 | 20 70 61 74 63 68 20 6c |sion and| patch l|
|00001340| 65 76 65 6c 20 6f 66 20 | 74 68 65 20 70 72 6f 67 |evel of |the prog|
|00001350| 72 61 6d 0a 58 69 73 20 | 70 72 69 6e 74 65 64 3b |ram.Xis |printed;|
|00001360| 20 74 68 65 20 72 65 73 | 6f 6c 75 74 69 6f 6e 20 | the res|olution |
|00001370| 6f 66 20 74 68 65 20 63 | 6c 6f 63 6b 20 69 73 20 |of the c|lock is |
|00001380| 70 72 69 6e 74 65 64 3b | 20 74 68 65 20 73 69 7a |printed;| the siz|
|00001390| 65 20 6f 66 20 74 68 65 | 0a 58 65 6c 65 6d 65 6e |e of the|.Xelemen|
|000013a0| 74 73 20 69 73 20 72 65 | 70 6f 72 74 65 64 3b 20 |ts is re|ported; |
|000013b0| 61 6e 64 20 74 68 65 20 | 6e 75 6d 62 65 72 20 6f |and the |number o|
|000013c0| 66 20 65 6c 65 6d 65 6e | 74 73 20 74 6f 20 62 65 |f elemen|ts to be|
|000013d0| 20 73 6f 72 74 65 64 20 | 69 73 0a 58 72 65 70 6f | sorted |is.Xrepo|
|000013e0| 72 74 65 64 2e 0a 58 0a | 58 20 20 20 20 46 6f 72 |rted..X.|X    For|
|000013f0| 20 65 61 63 68 20 73 6f | 72 74 20 61 6c 67 6f 72 | each so|rt algor|
|00001400| 69 74 68 6d 2c 20 61 20 | 74 61 62 6c 65 20 6f 66 |ithm, a |table of|
|00001410| 20 6d 65 61 73 75 72 65 | 6d 65 6e 74 73 20 69 73 | measure|ments is|
|00001420| 20 72 65 70 6f 72 74 65 | 64 2e 20 20 54 68 65 0a | reporte|d.  The.|
|00001430| 58 72 6f 77 73 20 64 65 | 73 63 72 69 62 65 20 74 |Xrows de|scribe t|
|00001440| 68 65 20 73 69 74 75 61 | 74 69 6f 6e 20 74 68 65 |he situa|tion the|
|00001450| 20 73 6f 72 74 20 61 6c | 67 6f 72 69 74 68 6d 20 | sort al|gorithm |
|00001460| 77 61 73 20 70 72 65 73 | 65 6e 74 65 64 20 77 69 |was pres|ented wi|
|00001470| 74 68 20 66 6f 72 0a 58 | 74 68 6f 73 65 20 6d 65 |th for.X|those me|
|00001480| 61 73 75 72 65 6d 65 6e | 74 73 20 61 6e 64 20 74 |asuremen|ts and t|
|00001490| 68 65 20 63 6f 6c 75 6d | 6e 73 20 72 65 70 72 65 |he colum|ns repre|
|000014a0| 73 65 6e 74 20 74 68 65 | 20 74 79 70 65 20 6f 66 |sent the| type of|
|000014b0| 20 6d 65 61 73 75 72 65 | 6d 65 6e 74 0a 58 74 61 | measure|ment.Xta|
|000014c0| 6b 65 6e 2e 20 20 54 68 | 65 20 72 6f 77 73 20 28 |ken.  Th|e rows (|
|000014d0| 73 69 74 75 61 74 69 6f | 6e 73 29 20 61 72 65 3a |situatio|ns) are:|
|000014e0| 0a 58 0a 58 20 20 20 20 | 72 61 6e 64 6f 6d 3a 20 |.X.X    |random: |
|000014f0| 20 20 54 68 65 20 63 6f | 6e 74 65 6e 74 73 20 6f |  The co|ntents o|
|00001500| 66 20 74 68 65 20 61 72 | 72 61 79 20 74 6f 20 62 |f the ar|ray to b|
|00001510| 65 20 73 6f 72 74 65 64 | 20 61 72 65 20 70 73 65 |e sorted| are pse|
|00001520| 75 64 6f 20 0a 58 20 20 | 20 20 20 20 20 20 20 20 |udo .X  |        |
|00001530| 20 20 20 20 72 61 6e 64 | 6f 6d 20 6e 75 6d 62 65 |    rand|om numbe|
|00001540| 72 73 20 67 65 6e 65 72 | 61 74 65 64 20 62 79 20 |rs gener|ated by |
|00001550| 72 61 6e 64 28 29 2c 20 | 77 69 74 68 20 74 77 6f |rand(), |with two|
|00001560| 20 73 70 65 63 69 61 6c | 0a 58 20 20 20 20 20 20 | special|.X      |
|00001570| 20 20 20 20 20 20 20 20 | 76 61 6c 75 65 73 20 65 |        |values e|
|00001580| 78 63 6c 75 64 65 64 20 | 66 6f 72 20 74 68 65 20 |xcluded |for the |
|00001590| 70 75 72 70 6f 73 65 20 | 6f 66 20 64 65 74 65 63 |purpose |of detec|
|000015a0| 74 69 6e 67 20 6f 76 65 | 72 77 72 69 74 65 73 0a |ting ove|rwrites.|
|000015b0| 58 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 61 |X       |       a|
|000015c0| 74 20 74 68 65 20 65 6e | 64 73 20 6f 66 20 74 68 |t the en|ds of th|
|000015d0| 65 20 61 72 72 61 79 2e | 0a 58 20 20 20 20 61 73 |e array.|.X    as|
|000015e0| 63 65 6e 64 3a 20 20 20 | 54 68 65 20 61 72 72 61 |cend:   |The arra|
|000015f0| 79 20 69 73 20 61 6c 72 | 65 61 64 79 20 63 6f 6d |y is alr|eady com|
|00001600| 70 6c 65 74 65 6c 79 20 | 69 6e 20 6f 72 64 65 72 |pletely |in order|
|00001610| 2e 20 20 54 6f 20 73 69 | 6d 70 6c 79 0a 58 20 20 |.  To si|mply.X  |
|00001620| 20 20 20 20 20 20 20 20 | 20 20 20 20 76 65 72 69 |        |    veri|
|00001630| 66 79 20 74 68 69 73 20 | 66 61 63 74 20 69 73 20 |fy this |fact is |
|00001640| 61 6c 6c 20 74 68 61 74 | 27 73 20 72 65 71 75 69 |all that|'s requi|
|00001650| 72 65 64 20 6f 66 20 74 | 68 65 20 73 6f 72 74 0a |red of t|he sort.|
|00001660| 58 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 61 |X       |       a|
|00001670| 6c 67 6f 72 69 74 68 6d | 3b 20 69 72 6f 6e 69 63 |lgorithm|; ironic|
|00001680| 61 6c 6c 79 2c 20 62 75 | 62 62 6c 65 20 73 6f 72 |ally, bu|bble sor|
|00001690| 74 20 6f 75 74 70 65 72 | 66 6f 72 6d 73 20 61 6c |t outper|forms al|
|000016a0| 6c 0a 58 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |l.X     |        |
|000016b0| 20 74 68 65 20 72 65 73 | 74 20 69 6e 20 74 68 69 | the res|t in thi|
|000016c0| 73 20 63 61 73 65 2e 0a | 58 20 20 20 20 64 65 73 |s case..|X    des|
|000016d0| 63 65 6e 64 3a 20 20 54 | 68 65 20 61 72 72 61 79 |cend:  T|he array|
|000016e0| 20 69 73 20 65 78 61 63 | 74 6c 79 20 69 6e 20 72 | is exac|tly in r|
|000016f0| 65 76 65 72 73 65 20 6f | 72 64 65 72 2e 20 20 54 |everse o|rder.  T|
|00001700| 68 65 6f 72 65 74 69 63 | 61 6c 6c 79 2c 0a 58 20 |heoretic|ally,.X |
|00001710| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 61 6e 20 |        |     an |
|00001720| 73 6f 72 74 20 66 75 6e | 63 74 69 6f 6e 20 63 6f |sort fun|ction co|
|00001730| 75 6c 64 20 64 65 74 65 | 63 74 20 74 68 69 73 20 |uld dete|ct this |
|00001740| 61 6e 64 20 73 77 61 70 | 20 65 6e 64 73 20 69 6e |and swap| ends in|
|00001750| 0a 58 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |.X      |        |
|00001760| 6c 69 6e 65 61 72 20 74 | 69 6d 65 2c 20 62 75 74 |linear t|ime, but|
|00001770| 20 69 74 20 68 61 72 64 | 6c 79 20 73 65 65 6d 73 | it hard|ly seems|
|00001780| 20 75 73 65 66 75 6c 2e | 0a 58 20 20 20 20 66 69 | useful.|.X    fi|
|00001790| 62 20 61 73 63 3a 20 20 | 54 68 65 20 63 6f 6e 74 |b asc:  |The cont|
|000017a0| 65 6e 74 73 20 6f 66 20 | 74 68 65 20 61 72 72 61 |ents of |the arra|
|000017b0| 79 20 61 72 65 20 69 72 | 72 65 6c 65 76 61 6e 74 |y are ir|relevant|
|000017c0| 3b 20 74 68 65 20 63 6f | 6d 70 61 72 69 73 6f 6e |; the co|mparison|
|000017d0| 0a 58 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |.X      |        |
|000017e0| 66 75 6e 63 74 69 6f 6e | 20 70 61 73 73 65 64 20 |function| passed |
|000017f0| 74 6f 20 74 68 65 20 72 | 6f 75 74 69 6e 65 20 61 |to the r|outine a|
|00001800| 6c 77 61 79 73 20 73 61 | 79 73 20 74 68 61 74 20 |lways sa|ys that |
|00001810| 69 74 73 0a 58 20 20 20 | 20 20 20 20 20 20 20 20 |its.X   |        |
|00001820| 20 20 20 66 69 72 73 74 | 20 61 72 67 75 6d 65 6e |   first| argumen|
|00001830| 74 20 69 73 20 6c 65 73 | 73 20 74 68 61 6e 20 69 |t is les|s than i|
|00001840| 74 73 20 73 65 63 6f 6e | 64 2e 0a 58 20 20 20 20 |ts secon|d..X    |
|00001850| 66 69 62 20 64 65 73 63 | 3a 20 53 69 6d 69 6c 61 |fib desc|: Simila|
|00001860| 72 6c 79 2c 20 74 68 65 | 20 63 6f 6d 70 61 72 69 |rly, the| compari|
|00001870| 73 6f 6e 20 66 75 6e 63 | 74 69 6f 6e 20 61 6c 77 |son func|tion alw|
|00001880| 61 79 73 20 73 61 79 73 | 20 74 68 61 74 20 69 74 |ays says| that it|
|00001890| 73 0a 58 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |s.X     |        |
|000018a0| 20 66 69 72 73 74 20 61 | 72 67 75 6d 65 6e 74 20 | first a|rgument |
|000018b0| 69 73 20 67 72 65 61 74 | 65 72 20 74 68 61 6e 20 |is great|er than |
|000018c0| 69 74 73 20 73 65 63 6f | 6e 64 2e 0a 58 20 20 20 |its seco|nd..X   |
|000018d0| 20 73 75 72 70 72 69 73 | 65 3a 20 41 20 70 73 65 | surpris|e: A pse|
|000018e0| 75 64 6f 72 61 6e 64 6f | 6d 20 72 65 73 75 6c 74 |udorando|m result|
|000018f0| 20 69 73 20 72 65 74 75 | 72 6e 65 64 20 66 72 6f | is retu|rned fro|
|00001900| 6d 20 74 68 65 20 63 6f | 6d 70 61 72 69 73 6f 6e |m the co|mparison|
|00001910| 20 0a 58 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | .X     |        |
|00001920| 20 66 75 6e 63 74 69 6f | 6e 20 69 6e 20 61 6e 20 | functio|n in an |
|00001930| 61 74 74 65 6d 70 74 20 | 74 6f 20 63 6f 6e 66 6f |attempt |to confo|
|00001940| 75 6e 64 20 74 68 65 20 | 61 6c 67 6f 72 69 74 68 |und the |algorith|
|00001950| 6d 73 27 20 65 66 66 6f | 72 74 73 0a 58 20 20 20 |ms' effo|rts.X   |
|00001960| 20 20 20 20 20 20 20 20 | 20 20 20 61 74 20 73 6f |        |   at so|
|00001970| 72 74 69 6e 67 2e 0a 58 | 20 20 20 20 6d 6f 73 74 |rting..X|    most|
|00001980| 6c 79 3a 20 20 20 53 69 | 6d 69 6c 61 72 20 74 6f |ly:   Si|milar to|
|00001990| 20 61 73 63 65 6e 64 2c | 20 62 75 74 20 74 68 65 | ascend,| but the|
|000019a0| 20 66 69 72 73 74 20 61 | 6e 64 20 6c 61 73 74 20 | first a|nd last |
|000019b0| 65 6c 65 6d 65 6e 74 73 | 0a 58 20 20 20 20 20 20 |elements|.X      |
|000019c0| 20 20 20 20 20 20 20 20 | 61 72 65 20 72 65 76 65 |        |are reve|
|000019d0| 72 73 65 64 2e 20 20 54 | 68 69 73 20 69 73 20 6d |rsed.  T|his is m|
|000019e0| 65 61 6e 74 20 74 6f 20 | 73 69 6d 75 6c 61 74 65 |eant to |simulate|
|000019f0| 20 61 6e 20 69 6e 64 65 | 78 20 77 68 69 63 68 0a | an inde|x which.|
|00001a00| 58 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 69 |X       |       i|
|00001a10| 73 20 70 72 65 74 74 79 | 20 6d 75 63 68 20 61 6c |s pretty| much al|
|00001a20| 72 65 61 64 79 20 73 6f | 72 74 65 64 20 61 6e 64 |ready so|rted and|
|00001a30| 20 6f 6e 6c 79 20 61 20 | 73 6d 61 6c 6c 20 6e 75 | only a |small nu|
|00001a40| 6d 62 65 72 0a 58 20 20 | 20 20 20 20 20 20 20 20 |mber.X  |        |
|00001a50| 20 20 20 20 6f 66 20 6e | 65 77 20 69 74 65 6d 73 |    of n|ew items|
|00001a60| 20 6e 65 65 64 20 74 6f | 20 62 65 20 69 6e 73 65 | need to| be inse|
|00001a70| 72 74 65 64 2e 0a 58 20 | 20 20 20 65 71 75 69 76 |rted..X |   equiv|
|00001a80| 3a 20 20 20 20 54 68 65 | 20 63 6f 6d 70 61 72 69 |:    The| compari|
|00001a90| 73 6f 6e 20 66 75 6e 63 | 74 69 6f 6e 20 72 65 70 |son func|tion rep|
|00001aa0| 6f 72 74 73 20 74 68 61 | 74 20 61 6c 6c 20 65 6c |orts tha|t all el|
|00001ab0| 65 6d 65 6e 74 73 20 0a | 58 20 20 20 20 20 20 20 |ements .|X       |
|00001ac0| 20 20 20 20 20 20 20 63 | 6f 6d 70 61 72 65 20 65 |       c|ompare e|
|00001ad0| 71 75 61 6c 2e 20 20 54 | 68 65 20 64 61 74 61 20 |qual.  T|he data |
|00001ae0| 69 73 20 61 72 72 61 6e | 67 65 64 20 73 6f 20 74 |is arran|ged so t|
|00001af0| 68 61 74 20 61 0a 58 20 | 20 20 20 20 20 20 20 20 |hat a.X |        |
|00001b00| 20 20 20 20 20 63 68 65 | 63 6b 20 63 61 6e 20 62 |     che|ck can b|
|00001b10| 65 20 6d 61 64 65 20 66 | 6f 72 20 77 68 65 74 68 |e made f|or wheth|
|00001b20| 65 72 20 74 68 65 20 61 | 6c 67 6f 72 69 74 68 6d |er the a|lgorithm|
|00001b30| 20 69 73 0a 58 20 20 20 | 20 20 20 20 20 20 20 20 | is.X   |        |
|00001b40| 20 20 20 73 74 61 62 6c | 65 3b 20 74 68 61 74 20 |   stabl|e; that |
|00001b50| 69 73 20 74 68 65 20 70 | 72 6f 70 65 72 74 79 20 |is the p|roperty |
|00001b60| 74 68 61 74 20 72 65 63 | 6f 72 64 73 20 77 69 74 |that rec|ords wit|
|00001b70| 68 0a 58 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |h.X     |        |
|00001b80| 20 65 71 75 61 6c 20 6b | 65 79 73 20 73 74 61 79 | equal k|eys stay|
|00001b90| 20 69 6e 20 74 68 65 20 | 73 61 6d 65 20 72 65 6c | in the |same rel|
|00001ba0| 61 74 69 76 65 20 6f 72 | 64 65 72 20 69 6e 20 74 |ative or|der in t|
|00001bb0| 68 65 0a 58 20 20 20 20 | 20 20 20 20 20 20 20 20 |he.X    |        |
|00001bc0| 20 20 61 72 72 61 79 20 | 74 68 61 74 20 74 68 65 |  array |that the|
|00001bd0| 79 20 77 65 72 65 20 69 | 6e 20 62 65 66 6f 72 65 |y were i|n before|
|00001be0| 20 74 68 65 20 73 6f 72 | 74 20 62 65 67 61 6e 2e | the sor|t began.|
|00001bf0| 0a 58 0a 58 54 68 65 20 | 63 6f 6c 75 6d 6e 73 20 |.X.XThe |columns |
|00001c00| 72 65 66 65 72 20 74 6f | 20 74 68 65 73 65 20 6d |refer to| these m|
|00001c10| 65 61 73 75 72 65 6d 65 | 6e 74 73 3a 0a 58 0a 58 |easureme|nts:.X.X|
|00001c20| 20 20 20 20 63 6f 6d 70 | 61 72 65 73 3a 20 54 68 |    comp|ares: Th|
|00001c30| 65 20 6e 75 6d 62 65 72 | 20 6f 66 20 63 61 6c 6c |e number| of call|
|00001c40| 73 20 74 6f 20 74 68 65 | 20 63 6f 6d 70 61 72 69 |s to the| compari|
|00001c50| 73 6f 6e 20 72 6f 75 74 | 69 6e 65 20 64 75 72 69 |son rout|ine duri|
|00001c60| 6e 67 0a 58 20 20 20 20 | 20 20 20 20 20 20 20 20 |ng.X    |        |
|00001c70| 20 20 74 68 65 20 73 6f | 72 74 2e 20 20 49 20 63 |  the so|rt.  I c|
|00001c80| 6f 6e 73 69 64 65 72 20 | 74 68 69 73 20 76 65 72 |onsider |this ver|
|00001c90| 79 20 69 6d 70 6f 72 74 | 61 6e 74 2c 20 61 73 20 |y import|ant, as |
|00001ca0| 6d 6f 73 74 0a 58 20 20 | 20 20 20 20 20 20 20 20 |most.X  |        |
|00001cb0| 20 20 20 20 6f 66 20 74 | 68 65 20 73 6f 72 74 69 |    of t|he sorti|
|00001cc0| 6e 67 20 62 6f 74 74 6c | 65 6e 65 63 6b 73 20 49 |ng bottl|enecks I|
|00001cd0| 27 76 65 20 65 78 70 65 | 72 69 65 6e 63 65 20 63 |'ve expe|rience c|
|00001ce0| 65 6e 74 65 72 0a 58 20 | 20 20 20 20 20 20 20 20 |enter.X |        |
|00001cf0| 20 20 20 20 20 61 72 6f | 75 6e 64 20 74 68 65 20 |     aro|und the |
|00001d00| 63 6f 6d 70 61 72 69 73 | 6f 6e 20 66 75 6e 63 74 |comparis|on funct|
|00001d10| 69 6f 6e 2e 0a 58 20 20 | 20 20 73 74 61 63 6b 3a |ion..X  |  stack:|
|00001d20| 20 20 20 20 28 45 73 74 | 69 6d 61 74 65 64 29 20 |    (Est|imated) |
|00001d30| 53 6f 6d 65 20 73 65 6d | 69 2d 6e 6f 6e 2d 70 6f |Some sem|i-non-po|
|00001d40| 72 74 61 62 6c 65 20 61 | 74 74 65 6d 70 74 73 20 |rtable a|ttempts |
|00001d50| 74 6f 20 72 65 63 6f 72 | 64 0a 58 20 20 20 20 20 |to recor|d.X     |
|00001d60| 20 20 20 20 20 20 20 20 | 20 74 68 65 20 67 72 6f |        | the gro|
|00001d70| 77 74 68 20 6f 66 20 74 | 68 65 20 73 74 61 63 6b |wth of t|he stack|
|00001d80| 20 61 72 65 20 6d 61 64 | 65 20 61 6e 64 20 61 20 | are mad|e and a |
|00001d90| 6e 75 6d 62 65 72 20 63 | 6f 6d 65 73 0a 58 20 20 |number c|omes.X  |
|00001da0| 20 20 20 20 20 20 20 20 | 20 20 20 20 6f 75 74 2e |        |    out.|
|00001db0| 20 20 49 20 63 6f 6e 73 | 69 64 65 72 20 4f 28 6c |  I cons|ider O(l|
|00001dc0| 6f 67 20 6e 29 20 75 73 | 65 20 6f 66 20 74 68 65 |og n) us|e of the|
|00001dd0| 20 73 74 61 63 6b 20 61 | 63 63 65 70 74 61 62 6c | stack a|cceptabl|
|00001de0| 65 0a 58 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |e.X     |        |
|00001df0| 20 6f 6e 20 6d 6f 64 65 | 72 6e 20 6d 61 63 68 69 | on mode|rn machi|
|00001e00| 6e 65 73 20 61 6e 64 20 | 6e 6f 6e 65 20 6f 66 20 |nes and |none of |
|00001e10| 74 68 65 73 65 20 61 6c | 67 6f 72 69 74 68 6d 73 |these al|gorithms|
|00001e20| 20 61 72 65 0a 58 20 20 | 20 20 20 20 20 20 20 20 | are.X  |        |
|00001e30| 20 20 20 20 77 6f 72 73 | 65 20 74 68 61 6e 20 74 |    wors|e than t|
|00001e40| 68 61 74 2e 20 0a 58 20 | 20 20 20 68 65 61 70 3a |hat. .X |   heap:|
|00001e50| 20 20 20 20 20 41 6d 6f | 75 6e 74 20 6f 66 20 6d |     Amo|unt of m|
|00001e60| 61 6c 6c 6f 63 27 64 20 | 73 74 6f 72 61 67 65 20 |alloc'd |storage |
|00001e70| 61 73 20 72 65 70 6f 72 | 74 65 64 20 62 79 20 6d |as repor|ted by m|
|00001e80| 61 6c 6c 69 6e 66 6f 28 | 29 2e 0a 58 20 20 20 20 |allinfo(|)..X    |
|00001e90| 20 20 20 20 20 20 20 20 | 20 20 49 66 20 79 6f 75 |        |  If you|
|00001ea0| 72 20 43 20 6c 69 62 72 | 61 72 79 20 64 6f 65 73 |r C libr|ary does|
|00001eb0| 6e 27 74 20 73 75 70 70 | 6f 72 74 20 6d 61 6c 6c |n't supp|ort mall|
|00001ec0| 69 6e 66 6f 28 29 2c 20 | 74 68 65 0a 58 20 20 20 |info(), |the.X   |
|00001ed0| 20 20 20 20 20 20 20 20 | 20 20 20 63 6f 6d 70 69 |        |   compi|
|00001ee0| 6c 65 72 20 77 69 6c 6c | 20 70 72 6f 62 61 62 6c |ler will| probabl|
|00001ef0| 79 20 62 61 72 66 20 6f | 6e 20 66 6c 6f 67 67 65 |y barf o|n flogge|
|00001f00| 72 2e 63 2e 20 20 54 68 | 65 20 66 6c 6f 67 67 65 |r.c.  Th|e flogge|
|00001f10| 72 0a 58 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |r.X     |        |
|00001f20| 20 63 68 65 63 6b 73 20 | 66 6f 72 20 6d 65 6d 6f | checks |for memo|
|00001f30| 72 79 20 6c 65 61 6b 73 | 2e 0a 58 20 20 20 20 75 |ry leaks|..X    u|
|00001f40| 73 65 72 3a 20 20 20 20 | 20 41 6d 6f 75 6e 74 20 |ser:    | Amount |
|00001f50| 6f 66 20 75 73 65 72 20 | 6d 6f 64 65 20 43 50 55 |of user |mode CPU|
|00001f60| 20 74 69 6d 65 20 61 73 | 20 72 65 70 6f 72 74 65 | time as| reporte|
|00001f70| 64 20 62 79 20 74 69 6d | 65 73 28 29 2e 0a 58 20 |d by tim|es()..X |
|00001f80| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 54 68 69 |        |     Thi|
|00001f90| 73 20 69 6e 63 6c 75 64 | 65 73 20 74 69 6d 65 20 |s includ|es time |
|00001fa0| 66 6f 72 20 62 6f 74 68 | 20 74 68 65 20 6f 70 65 |for both| the ope|
|00001fb0| 72 61 74 69 6f 6e 20 6f | 66 20 74 68 65 0a 58 20 |ration o|f the.X |
|00001fc0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 73 6f 72 |        |     sor|
|00001fd0| 74 20 66 75 6e 63 74 69 | 6f 6e 20 61 6e 64 20 74 |t functi|on and t|
|00001fe0| 68 65 20 63 6f 6d 70 61 | 72 69 73 6f 6e 20 66 75 |he compa|rison fu|
|00001ff0| 6e 63 74 69 6f 6e 3b 20 | 61 73 20 74 68 65 73 65 |nction; |as these|
|00002000| 0a 58 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |.X      |        |
|00002010| 61 72 65 20 6f 6e 6c 79 | 20 6d 61 72 67 69 6e 61 |are only| margina|
|00002020| 6c 6c 79 20 72 65 6c 61 | 74 65 64 2c 20 74 68 69 |lly rela|ted, thi|
|00002030| 73 20 6e 75 6d 62 65 72 | 20 69 73 20 6e 6f 74 0a |s number| is not.|
|00002040| 58 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 75 |X       |       u|
|00002050| 73 65 66 75 6c 20 66 6f | 72 20 65 73 74 69 6d 61 |seful fo|r estima|
|00002060| 74 69 6e 67 20 68 6f 77 | 20 6c 6f 6e 67 20 69 74 |ting how| long it|
|00002070| 20 6d 69 67 68 74 20 74 | 61 6b 65 20 74 6f 20 0a | might t|ake to .|
|00002080| 58 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 73 |X       |       s|
|00002090| 6f 72 74 20 75 73 65 66 | 75 6c 20 64 61 74 61 20 |ort usef|ul data |
|000020a0| 69 6e 20 73 6f 6d 65 20 | 6f 74 68 65 72 20 70 72 |in some |other pr|
|000020b0| 6f 67 72 61 6d 2e 0a 58 | 20 20 20 20 73 79 73 74 |ogram..X|    syst|
|000020c0| 65 6d 3a 20 20 20 41 6d | 6f 75 6e 74 20 6f 66 20 |em:   Am|ount of |
|000020d0| 73 79 73 74 65 6d 20 43 | 50 55 20 74 69 6d 65 20 |system C|PU time |
|000020e0| 61 73 20 72 65 70 6f 72 | 74 65 64 20 62 79 20 74 |as repor|ted by t|
|000020f0| 69 6d 65 73 28 29 2e 0a | 58 20 20 20 20 20 20 20 |imes()..|X       |
|00002100| 20 20 20 20 20 20 20 47 | 65 6e 65 72 61 6c 6c 79 |       G|enerally|
|00002110| 20 30 2e 30 30 20 6f 72 | 20 76 65 72 79 20 73 6d | 0.00 or| very sm|
|00002120| 61 6c 6c 2e 20 20 49 66 | 20 61 20 73 6f 72 74 20 |all.  If| a sort |
|00002130| 61 6c 67 6f 72 69 74 68 | 6d 0a 58 20 20 20 20 20 |algorith|m.X     |
|00002140| 20 20 20 20 20 20 20 20 | 20 75 73 65 73 20 6c 6f |        | uses lo|
|00002150| 74 73 20 6f 66 20 73 79 | 73 74 65 6d 20 74 69 6d |ts of sy|stem tim|
|00002160| 65 20 69 74 27 73 20 70 | 72 6f 62 61 62 6c 79 20 |e it's p|robably |
|00002170| 61 20 54 72 6f 6a 61 6e | 20 68 6f 72 73 65 0a 58 |a Trojan| horse.X|
|00002180| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 74 72 |        |      tr|
|00002190| 79 69 6e 67 20 74 6f 20 | 62 72 65 61 6b 20 69 6e |ying to |break in|
|000021a0| 74 6f 20 74 68 65 20 70 | 61 73 73 77 64 20 66 69 |to the p|asswd fi|
|000021b0| 6c 65 20 6f 72 20 64 65 | 6c 65 74 65 20 79 6f 75 |le or de|lete you|
|000021c0| 72 0a 58 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |r.X     |        |
|000021d0| 20 68 6f 6d 65 20 64 69 | 72 65 63 74 6f 72 79 20 | home di|rectory |
|000021e0| 6f 72 20 73 6f 6d 65 74 | 68 69 6e 67 20 73 6f 20 |or somet|hing so |
|000021f0| 6d 61 79 62 65 20 79 6f | 75 20 73 68 6f 75 6c 64 |maybe yo|u should|
|00002200| 0a 58 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |.X      |        |
|00002210| 73 74 61 72 74 20 73 68 | 75 66 66 6c 69 6e 67 20 |start sh|uffling |
|00002220| 74 68 72 6f 75 67 68 20 | 79 6f 75 72 20 64 65 73 |through |your des|
|00002230| 6b 20 6c 6f 6f 6b 69 6e | 67 20 66 6f 72 20 61 20 |k lookin|g for a |
|00002240| 72 65 63 65 6e 74 0a 58 | 20 20 20 20 20 20 20 20 |recent.X|        |
|00002250| 20 20 20 20 20 20 62 61 | 63 6b 75 70 20 74 61 70 |      ba|ckup tap|
|00002260| 65 2e 20 20 49 20 6d 61 | 79 20 72 65 6d 6f 76 65 |e.  I ma|y remove|
|00002270| 20 74 68 69 73 20 69 6e | 20 61 20 66 75 74 75 72 | this in| a futur|
|00002280| 65 20 76 65 72 73 69 6f | 6e 0a 58 20 20 20 20 20 |e versio|n.X     |
|00002290| 20 20 20 20 20 20 20 20 | 20 28 74 68 65 20 72 65 |        | (the re|
|000022a0| 70 6f 72 74 20 6f 66 20 | 73 79 73 74 65 6d 20 74 |port of |system t|
|000022b0| 69 6d 65 2c 20 6e 6f 74 | 20 74 68 65 20 54 72 6f |ime, not| the Tro|
|000022c0| 6a 61 6e 20 68 6f 72 73 | 65 29 0a 58 20 20 20 20 |jan hors|e).X    |
|000022d0| 20 20 20 20 20 20 20 20 | 20 20 69 6e 20 66 61 76 |        |  in fav|
|000022e0| 6f 72 20 6f 66 20 61 6e | 6f 74 68 65 72 20 6d 65 |or of an|other me|
|000022f0| 74 72 69 63 2c 20 70 65 | 72 68 61 70 73 20 77 61 |tric, pe|rhaps wa|
|00002300| 6c 6c 20 63 6c 6f 63 6b | 20 74 69 6d 65 2e 0a 58 |ll clock| time..X|
|00002310| 0a 58 20 20 20 20 42 75 | 74 20 69 74 20 69 73 6e |.X    Bu|t it isn|
|00002320| 27 74 20 65 6e 6f 75 67 | 68 20 73 69 6d 70 6c 79 |'t enoug|h simply|
|00002330| 20 74 6f 20 62 65 20 66 | 61 73 74 2c 20 61 20 73 | to be f|ast, a s|
|00002340| 6f 72 74 20 61 6c 67 6f | 72 69 74 68 6d 20 61 6c |ort algo|rithm al|
|00002350| 73 6f 20 68 61 73 0a 58 | 74 6f 20 62 65 20 63 6f |so has.X|to be co|
|00002360| 72 72 65 63 74 2e 20 20 | 54 6f 20 74 68 61 74 20 |rrect.  |To that |
|00002370| 65 6e 64 2c 20 74 68 65 | 20 66 6c 6f 67 67 65 72 |end, the| flogger|
|00002380| 20 72 6f 75 74 69 6e 65 | 20 76 65 72 69 66 69 65 | routine| verifie|
|00002390| 73 20 74 68 61 74 0a 58 | 74 68 65 20 61 72 72 61 |s that.X|the arra|
|000023a0| 79 20 77 61 73 20 61 63 | 74 75 61 6c 6c 79 20 73 |y was ac|tually s|
|000023b0| 6f 72 74 65 64 2c 20 61 | 74 20 6c 65 61 73 74 20 |orted, a|t least |
|000023c0| 77 68 65 6e 20 74 68 65 | 20 63 6f 6d 70 61 72 69 |when the| compari|
|000023d0| 73 6f 6e 20 72 6f 75 74 | 69 6e 65 0a 58 77 61 73 |son rout|ine.Xwas|
|000023e0| 6e 27 74 20 6c 79 69 6e | 67 2e 20 20 49 74 20 61 |n't lyin|g.  It a|
|000023f0| 6c 73 6f 20 63 68 65 63 | 6b 73 20 74 68 61 74 20 |lso chec|ks that |
|00002400| 6d 61 67 69 63 20 76 61 | 6c 75 65 73 20 69 6e 20 |magic va|lues in |
|00002410| 74 68 65 20 6d 65 6d 6f | 72 79 20 6c 6f 63 61 74 |the memo|ry locat|
|00002420| 69 6f 6e 73 0a 58 69 6d | 6d 65 64 69 61 74 65 6c |ions.Xim|mediatel|
|00002430| 79 20 61 62 6f 76 65 20 | 61 6e 64 20 62 65 6c 6f |y above |and belo|
|00002440| 77 20 74 68 65 20 61 72 | 72 61 79 20 77 65 72 65 |w the ar|ray were|
|00002450| 20 6e 6f 74 20 61 63 63 | 69 64 65 6e 74 61 6c 6c | not acc|identall|
|00002460| 79 20 61 63 63 65 73 73 | 65 64 0a 58 6f 72 20 6f |y access|ed.Xor o|
|00002470| 76 65 72 77 72 69 74 74 | 65 6e 2e 0a 58 0a 58 20 |verwritt|en..X.X |
|00002480| 20 20 20 54 68 65 20 62 | 6f 67 6f 20 73 6f 72 74 |   The b|ogo sort|
|00002490| 20 72 75 6e 20 69 73 20 | 73 6b 69 70 70 65 64 20 | run is |skipped |
|000024a0| 69 66 20 6e 20 69 73 20 | 73 75 66 66 69 63 69 65 |if n is |sufficie|
|000024b0| 6e 74 6c 79 20 6c 61 72 | 67 65 20 74 68 61 74 0a |ntly lar|ge that.|
|000024c0| 58 69 74 27 73 20 65 78 | 65 63 75 74 69 6f 6e 20 |Xit's ex|ecution |
|000024d0| 77 6f 75 6c 64 20 72 75 | 6e 20 69 6e 74 6f 20 74 |would ru|n into t|
|000024e0| 72 69 6c 6c 69 6f 6e 73 | 20 6f 66 20 63 79 63 6c |rillions| of cycl|
|000024f0| 65 73 20 28 61 70 70 72 | 6f 78 20 6e 20 3d 20 31 |es (appr|ox n = 1|
|00002500| 35 29 2e 0a 58 0a 58 4d | 49 53 43 45 4c 4c 41 4e |5)..X.XM|ISCELLAN|
|00002510| 45 4f 55 53 0a 58 0a 58 | 20 20 20 20 57 68 65 6e |EOUS.X.X|    When|
|00002520| 20 72 75 6e 6e 69 6e 67 | 20 74 68 65 20 74 65 73 | running| the tes|
|00002530| 74 20 72 6f 75 74 69 6e | 65 2c 20 73 6f 6d 65 20 |t routin|e, some |
|00002540| 73 6f 72 74 73 20 74 61 | 6b 65 20 73 6f 20 6c 6f |sorts ta|ke so lo|
|00002550| 6e 67 20 74 68 61 74 20 | 79 6f 75 0a 58 6d 69 67 |ng that |you.Xmig|
|00002560| 68 74 20 6c 6f 73 65 20 | 70 61 74 69 65 6e 63 65 |ht lose |patience|
|00002570| 2e 20 20 4b 65 79 62 6f | 61 72 64 20 69 6e 74 65 |.  Keybo|ard inte|
|00002580| 72 72 75 70 74 20 28 61 | 6b 61 20 43 6f 6e 74 72 |rrupt (a|ka Contr|
|00002590| 6f 6c 2d 43 29 20 77 69 | 6c 6c 20 61 62 6f 72 74 |ol-C) wi|ll abort|
|000025a0| 20 74 68 65 0a 58 63 75 | 72 72 65 6e 74 20 73 6f | the.Xcu|rrent so|
|000025b0| 72 74 20 74 65 73 74 20 | 61 6e 64 20 6d 6f 76 65 |rt test |and move|
|000025c0| 20 6f 6e 20 74 6f 20 74 | 68 65 20 6e 65 78 74 2e | on to t|he next.|
|000025d0| 20 20 49 66 20 79 6f 75 | 20 72 65 61 6c 6c 79 20 |  If you| really |
|000025e0| 77 61 6e 74 20 74 68 65 | 0a 58 70 72 6f 67 72 61 |want the|.Xprogra|
|000025f0| 6d 20 74 6f 20 65 6e 64 | 2c 20 67 69 76 65 20 69 |m to end|, give i|
|00002600| 74 20 61 20 71 75 69 74 | 20 73 69 67 6e 61 6c 20 |t a quit| signal |
|00002610| 28 43 6f 6e 74 72 6f 6c | 2d 5c 29 20 6f 72 20 73 |(Control|-\) or s|
|00002620| 65 6e 64 20 69 74 20 61 | 20 73 69 67 6e 61 6c 0a |end it a| signal.|
|00002630| 58 77 69 74 68 20 74 68 | 65 20 6b 69 6c 6c 20 63 |Xwith th|e kill c|
|00002640| 6f 6d 6d 61 6e 64 2e 20 | 20 20 59 6f 75 20 63 61 |ommand. |  You ca|
|00002650| 6e 20 61 6c 73 6f 20 62 | 61 63 6b 67 72 6f 75 6e |n also b|ackgroun|
|00002660| 64 20 69 74 20 28 43 6f | 6e 74 72 6f 6c 2d 5a 29 |d it (Co|ntrol-Z)|
|00002670| 20 66 72 6f 6d 0a 58 74 | 68 65 20 43 2d 73 68 65 | from.Xt|he C-she|
|00002680| 6c 6c 20 74 68 65 6e 20 | 6b 69 6c 6c 20 69 74 2e |ll then |kill it.|
|00002690| 0a 58 0a 58 20 20 20 20 | 54 68 65 20 73 69 7a 65 |.X.X    |The size|
|000026a0| 20 6f 66 20 74 68 65 20 | 65 6c 65 6d 65 6e 74 73 | of the |elements|
|000026b0| 20 62 65 69 6e 67 20 73 | 6f 72 74 65 64 20 69 73 | being s|orted is|
|000026c0| 20 68 61 72 64 2d 63 6f | 64 65 64 20 61 74 20 74 | hard-co|ded at t|
|000026d0| 68 65 20 6d 6f 6d 65 6e | 74 2c 0a 58 62 75 74 20 |he momen|t,.Xbut |
|000026e0| 69 74 20 63 61 6e 20 62 | 65 20 63 68 61 6e 67 65 |it can b|e change|
|000026f0| 64 20 62 79 20 67 6f 69 | 6e 67 20 69 6e 74 6f 20 |d by goi|ng into |
|00002700| 66 6c 6f 67 67 65 72 2e | 63 20 61 6e 64 20 63 68 |flogger.|c and ch|
|00002710| 61 6e 67 69 6e 67 20 74 | 68 65 20 74 79 70 65 64 |anging t|he typed|
|00002720| 65 66 73 20 66 6f 72 0a | 58 0a 58 20 20 20 20 23 |efs for.|X.X    #|
|00002730| 64 65 66 69 6e 65 20 54 | 45 53 54 5f 54 59 50 45 |define T|EST_TYPE|
|00002740| 20 64 6f 75 62 6c 65 0a | 58 20 20 20 20 23 64 65 | double.|X    #de|
|00002750| 66 69 6e 65 20 54 45 53 | 54 5f 46 55 4e 43 20 64 |fine TES|T_FUNC d|
|00002760| 6f 75 62 6c 65 5f 63 6f | 6d 70 61 72 65 0a 58 0a |ouble_co|mpare.X.|
|00002770| 58 69 6e 74 6f 0a 58 0a | 58 20 20 20 20 23 64 65 |Xinto.X.|X    #de|
|00002780| 66 69 6e 65 20 54 45 53 | 54 5f 54 59 50 45 20 69 |fine TES|T_TYPE i|
|00002790| 6e 74 0a 58 20 20 20 20 | 23 64 65 66 69 6e 65 20 |nt.X    |#define |
|000027a0| 54 45 53 54 5f 46 55 4e | 43 20 69 6e 74 5f 63 6f |TEST_FUN|C int_co|
|000027b0| 6d 70 61 72 65 0a 58 0a | 58 6f 72 20 62 61 63 6b |mpare.X.|Xor back|
|000027c0| 20 61 67 61 69 6e 2e 20 | 20 4f 72 20 61 64 64 20 | again. | Or add |
|000027d0| 61 20 6e 65 77 20 74 79 | 70 65 20 61 6e 64 20 61 |a new ty|pe and a|
|000027e0| 20 6e 65 77 20 63 6f 6d | 70 61 72 69 73 6f 6e 20 | new com|parison |
|000027f0| 66 75 6e 63 74 69 6f 6e | 2e 0a 58 0a 58 20 20 20 |function|..X.X   |
|00002800| 20 53 65 76 65 72 61 6c | 20 6f 66 20 74 68 65 20 | Several| of the |
|00002810| 73 6f 72 74 20 61 6c 67 | 6f 72 69 74 68 6d 73 20 |sort alg|orithms |
|00002820| 61 72 65 20 6e 6f 74 20 | 72 65 2d 65 6e 74 72 61 |are not |re-entra|
|00002830| 6e 74 20 77 68 69 63 68 | 20 6d 65 61 6e 73 0a 58 |nt which| means.X|
|00002840| 79 6f 75 20 73 68 6f 75 | 6c 64 6e 27 74 20 63 61 |you shou|ldn't ca|
|00002850| 6c 6c 20 74 68 65 20 73 | 6f 72 74 20 66 72 6f 6d |ll the s|ort from|
|00002860| 20 77 69 74 68 69 6e 20 | 74 68 65 20 76 65 72 79 | within |the very|
|00002870| 20 73 61 6d 65 20 63 6f | 6d 70 61 72 69 73 6f 6e | same co|mparison|
|00002880| 20 0a 58 66 75 6e 63 74 | 69 6f 6e 20 79 6f 75 20 | .Xfunct|ion you |
|00002890| 70 61 73 73 65 64 20 69 | 6e 74 6f 20 74 68 61 74 |passed i|nto that|
|000028a0| 20 73 6f 72 74 20 69 6e | 20 74 68 65 20 66 69 72 | sort in| the fir|
|000028b0| 73 74 20 70 6c 61 63 65 | 2e 0a 58 0a 58 43 4f 50 |st place|..X.XCOP|
|000028c0| 59 52 49 47 48 54 0a 58 | 0a 58 20 20 20 20 53 69 |YRIGHT.X|.X    Si|
|000028d0| 6e 63 65 20 6e 6f 6e 65 | 20 6f 66 20 74 68 65 20 |nce none| of the |
|000028e0| 73 6f 72 74 20 61 6c 67 | 6f 72 69 74 68 6d 73 20 |sort alg|orithms |
|000028f0| 61 72 65 20 6d 69 6e 65 | 20 61 6e 64 20 61 6e 79 |are mine| and any|
|00002900| 6f 6e 65 20 77 69 74 68 | 20 61 20 63 6f 70 79 0a |one with| a copy.|
|00002910| 58 6f 66 20 4b 6e 75 74 | 68 20 56 6f 6c 20 33 20 |Xof Knut|h Vol 3 |
|00002920| 61 6e 64 20 61 20 6c 69 | 74 74 6c 65 20 6b 6e 6f |and a li|ttle kno|
|00002930| 77 6c 65 64 67 65 20 6f | 66 20 43 20 63 6f 75 6c |wledge o|f C coul|
|00002940| 64 20 74 79 70 65 20 74 | 68 65 6d 20 69 6e 20 61 |d type t|hem in a|
|00002950| 73 20 65 61 73 69 6c 79 | 0a 58 61 73 20 49 20 64 |s easily|.Xas I d|
|00002960| 69 64 2c 20 74 68 65 72 | 65 20 69 73 6e 27 74 20 |id, ther|e isn't |
|00002970| 6d 75 63 68 20 70 6f 69 | 6e 74 20 69 6e 20 63 6c |much poi|nt in cl|
|00002980| 61 69 6d 69 6e 67 20 61 | 20 63 6f 70 79 72 69 67 |aiming a| copyrig|
|00002990| 68 74 2c 20 6d 75 63 68 | 20 6c 65 73 73 0a 58 61 |ht, much| less.Xa|
|000029a0| 70 70 6c 79 69 6e 67 20 | 66 6f 72 20 61 20 70 61 |pplying |for a pa|
|000029b0| 74 65 6e 74 2e 20 20 49 | 20 77 61 6e 74 65 64 20 |tent.  I| wanted |
|000029c0| 74 6f 20 64 69 73 63 6c | 61 69 6d 20 6c 69 61 62 |to discl|aim liab|
|000029d0| 69 6c 69 74 79 20 74 68 | 6f 75 67 68 2c 20 73 6f |ility th|ough, so|
|000029e0| 20 49 20 70 75 74 0a 58 | 61 20 66 65 77 20 6d 69 | I put.X|a few mi|
|000029f0| 6e 6f 72 20 72 65 73 74 | 72 69 63 74 69 6f 6e 73 |nor rest|rictions|
|00002a00| 20 6f 6e 20 74 68 65 20 | 63 6f 64 65 2c 20 61 73 | on the |code, as|
|00002a10| 20 73 65 74 20 66 6f 72 | 74 68 20 69 6e 20 65 61 | set for|th in ea|
|00002a20| 63 68 20 6f 66 20 74 68 | 65 0a 58 73 6f 75 72 63 |ch of th|e.Xsourc|
|00002a30| 65 20 66 69 6c 65 73 2e | 0a 45 4e 44 5f 4f 46 5f |e files.|.END_OF_|
|00002a40| 46 49 4c 45 0a 20 20 69 | 66 20 74 65 73 74 20 37 |FILE.  i|f test 7|
|00002a50| 39 39 33 20 2d 6e 65 20 | 60 77 63 20 2d 63 20 3c |993 -ne |`wc -c <|
|00002a60| 27 52 45 41 44 4d 45 27 | 60 3b 20 74 68 65 6e 0a |'README'|`; then.|
|00002a70| 20 20 20 20 65 63 68 6f | 20 73 68 61 72 3a 20 5c |    echo| shar: \|
|00002a80| 22 27 52 45 41 44 4d 45 | 27 5c 22 20 75 6e 70 61 |"'README|'\" unpa|
|00002a90| 63 6b 65 64 20 77 69 74 | 68 20 77 72 6f 6e 67 20 |cked wit|h wrong |
|00002aa0| 73 69 7a 65 21 0a 20 20 | 66 69 0a 20 20 23 20 65 |size!.  |fi.  # e|
|00002ab0| 6e 64 20 6f 66 20 27 52 | 45 41 44 4d 45 27 0a 66 |nd of 'R|EADME'.f|
|00002ac0| 69 0a 69 66 20 74 65 73 | 74 20 2d 66 20 27 4f 50 |i.if tes|t -f 'OP|
|00002ad0| 54 49 4d 49 5a 49 4e 47 | 27 20 2d 61 20 22 24 7b |TIMIZING|' -a "${|
|00002ae0| 31 7d 22 20 21 3d 20 22 | 2d 63 22 20 3b 20 74 68 |1}" != "|-c" ; th|
|00002af0| 65 6e 20 0a 20 20 65 63 | 68 6f 20 73 68 61 72 3a |en .  ec|ho shar:|
|00002b00| 20 57 69 6c 6c 20 6e 6f | 74 20 63 6c 6f 62 62 65 | Will no|t clobbe|
|00002b10| 72 20 65 78 69 73 74 69 | 6e 67 20 66 69 6c 65 20 |r existi|ng file |
|00002b20| 5c 22 27 4f 50 54 49 4d | 49 5a 49 4e 47 27 5c 22 |\"'OPTIM|IZING'\"|
|00002b30| 0a 65 6c 73 65 0a 20 20 | 65 63 68 6f 20 73 68 61 |.else.  |echo sha|
|00002b40| 72 3a 20 45 78 74 72 61 | 63 74 69 6e 67 20 5c 22 |r: Extra|cting \"|
|00002b50| 27 4f 50 54 49 4d 49 5a | 49 4e 47 27 5c 22 20 5c |'OPTIMIZ|ING'\" \|
|00002b60| 28 34 34 35 32 20 63 68 | 61 72 61 63 74 65 72 73 |(4452 ch|aracters|
|00002b70| 5c 29 0a 20 20 73 65 64 | 20 22 73 2f 5e 58 2f 2f |\).  sed| "s/^X//|
|00002b80| 22 20 3e 27 4f 50 54 49 | 4d 49 5a 49 4e 47 27 20 |" >'OPTI|MIZING' |
|00002b90| 3c 3c 27 45 4e 44 5f 4f | 46 5f 46 49 4c 45 27 0a |<<'END_O|F_FILE'.|
|00002ba0| 58 0a 58 41 20 62 72 69 | 65 66 20 77 6f 72 64 20 |X.XA bri|ef word |
|00002bb0| 61 62 6f 75 74 20 6f 70 | 74 69 6d 69 7a 69 6e 67 |about op|timizing|
|00002bc0| 20 63 6f 64 65 2c 20 69 | 6e 20 70 61 72 74 69 63 | code, i|n partic|
|00002bd0| 75 6c 61 72 2c 20 63 6f | 64 65 20 74 68 61 74 0a |ular, co|de that.|
|00002be0| 58 63 61 6c 6c 73 20 61 | 20 73 6f 72 74 69 6e 67 |Xcalls a| sorting|
|00002bf0| 20 66 75 6e 63 74 69 6f | 6e 2e 0a 58 0a 58 54 68 | functio|n..X.XTh|
|00002c00| 65 20 71 73 6f 72 74 28 | 29 20 74 68 61 74 20 63 |e qsort(|) that c|
|00002c10| 6f 6d 65 73 20 77 69 74 | 68 20 6d 6f 73 74 20 43 |omes wit|h most C|
|00002c20| 20 69 6d 70 6c 65 6d 65 | 6e 74 61 74 69 6f 6e 73 | impleme|ntations|
|00002c30| 20 69 73 20 66 61 73 74 | 20 65 6e 6f 75 67 68 20 | is fast| enough |
|00002c40| 66 6f 72 0a 58 6e 65 61 | 72 6c 79 20 61 6c 6c 20 |for.Xnea|rly all |
|00002c50| 70 75 72 70 6f 73 65 73 | 2e 20 20 54 68 65 20 73 |purposes|.  The s|
|00002c60| 6f 72 74 20 61 6c 67 6f | 72 69 74 68 6d 73 20 69 |ort algo|rithms i|
|00002c70| 6e 20 74 68 69 73 20 70 | 61 63 6b 61 67 65 20 61 |n this p|ackage a|
|00002c80| 72 65 20 68 65 72 65 0a | 58 6d 6f 73 74 6c 79 20 |re here.|Xmostly |
|00002c90| 66 6f 72 20 69 6e 74 65 | 6c 6c 65 63 74 75 61 6c |for inte|llectual|
|00002ca0| 20 63 75 72 69 6f 75 73 | 69 74 79 2e 20 20 54 68 | curious|ity.  Th|
|00002cb0| 65 20 6d 65 72 67 65 5f | 73 6f 72 74 20 61 6c 67 |e merge_|sort alg|
|00002cc0| 6f 72 69 74 68 6d 20 69 | 73 0a 58 73 75 70 65 72 |orithm i|s.Xsuper|
|00002cd0| 69 6f 72 20 69 6e 20 73 | 6f 6d 65 20 77 61 79 73 |ior in s|ome ways|
|00002ce0| 2c 20 6d 6f 73 74 6c 79 | 20 74 68 61 74 20 69 74 |, mostly| that it|
|00002cf0| 20 72 65 71 75 69 72 65 | 73 20 66 65 77 65 72 20 | require|s fewer |
|00002d00| 63 61 6c 6c 62 61 63 6b | 73 20 74 6f 20 74 68 65 |callback|s to the|
|00002d10| 0a 58 63 6f 6d 70 61 72 | 69 73 6f 6e 20 66 75 6e |.Xcompar|ison fun|
|00002d20| 63 74 69 6f 6e 2c 20 62 | 75 74 20 74 68 61 74 20 |ction, b|ut that |
|00002d30| 61 6c 6f 6e 65 20 69 73 | 20 6e 6f 20 72 65 61 73 |alone is| no reas|
|00002d40| 6f 6e 20 74 6f 20 73 65 | 64 20 2d 65 20 73 2f 71 |on to se|d -e s/q|
|00002d50| 73 6f 72 74 2f 6d 65 72 | 67 65 5f 73 6f 72 74 2f |sort/mer|ge_sort/|
|00002d60| 0a 58 6f 76 65 72 20 61 | 6c 6c 20 79 6f 75 72 20 |.Xover a|ll your |
|00002d70| 63 6f 64 65 2e 0a 58 0a | 58 53 6f 6d 65 20 67 65 |code..X.|XSome ge|
|00002d80| 6e 65 72 61 6c 20 61 70 | 70 72 6f 61 63 68 65 73 |neral ap|proaches|
|00002d90| 20 74 6f 20 63 6f 6e 73 | 69 64 65 72 20 62 65 66 | to cons|ider bef|
|00002da0| 6f 72 65 20 62 6f 72 72 | 6f 77 69 6e 67 20 6f 6e |ore borr|owing on|
|00002db0| 65 20 6f 66 20 74 68 65 | 73 65 0a 58 73 6f 72 74 |e of the|se.Xsort|
|00002dc0| 20 61 6c 67 6f 72 69 74 | 68 6d 73 20 66 6f 72 20 | algorit|hms for |
|00002dd0| 75 73 65 20 69 6e 20 79 | 6f 75 72 20 63 6f 64 65 |use in y|our code|
|00002de0| 2c 20 61 70 70 72 6f 78 | 69 6d 61 74 65 6c 79 20 |, approx|imately |
|00002df0| 69 6e 20 64 65 63 72 65 | 61 73 69 6e 67 0a 58 6f |in decre|asing.Xo|
|00002e00| 72 64 65 72 20 6f 66 20 | 65 66 66 65 63 74 69 76 |rder of |effectiv|
|00002e10| 65 6e 65 73 73 3a 0a 58 | 0a 58 31 2e 20 72 75 6e |eness:.X|.X1. run|
|00002e20| 20 70 72 6f 66 20 6f 72 | 20 67 70 72 6f 66 20 74 | prof or| gprof t|
|00002e30| 6f 20 6d 61 6b 65 20 73 | 75 72 65 20 74 68 65 20 |o make s|ure the |
|00002e40| 73 6f 72 74 69 6e 67 20 | 69 73 20 61 6e 20 61 63 |sorting |is an ac|
|00002e50| 74 75 61 6c 0a 58 20 20 | 20 62 6f 74 74 6c 65 6e |tual.X  | bottlen|
|00002e60| 65 63 6b 3b 20 6f 66 74 | 65 6e 2c 20 72 65 61 64 |eck; oft|en, read|
|00002e70| 69 6e 67 20 69 6e 20 74 | 68 65 20 72 65 63 6f 72 |ing in t|he recor|
|00002e80| 64 73 20 74 6f 20 62 65 | 20 73 6f 72 74 65 64 0a |ds to be| sorted.|
|00002e90| 58 20 20 20 74 61 6b 65 | 73 20 6d 6f 72 65 20 77 |X   take|s more w|
|00002ea0| 61 6c 6c 20 63 6c 6f 63 | 6b 20 74 69 6d 65 20 74 |all cloc|k time t|
|00002eb0| 68 61 6e 20 74 68 65 20 | 73 6f 72 74 20 69 74 73 |han the |sort its|
|00002ec0| 65 6c 66 20 61 6e 64 20 | 65 66 66 6f 72 74 0a 58 |elf and |effort.X|
|00002ed0| 20 20 20 73 70 65 6e 74 | 20 6f 70 74 69 6d 69 7a |   spent| optimiz|
|00002ee0| 69 6e 67 20 74 68 65 20 | 73 6f 72 74 20 69 73 20 |ing the |sort is |
|00002ef0| 63 6f 6d 70 6c 65 74 65 | 6c 79 20 70 6f 69 6e 74 |complete|ly point|
|00002f00| 6c 65 73 73 2e 0a 58 0a | 58 32 2e 20 55 73 65 20 |less..X.|X2. Use |
|00002f10| 79 6f 75 72 20 63 6f 6d | 70 69 6c 65 72 27 73 20 |your com|piler's |
|00002f20| 6d 61 78 69 6d 61 6c 20 | 6f 70 74 69 6d 69 7a 61 |maximal |optimiza|
|00002f30| 74 69 6f 6e 20 6c 65 76 | 65 6c 20 77 68 65 6e 20 |tion lev|el when |
|00002f40| 63 6f 6d 70 69 6c 69 6e | 67 0a 58 20 20 20 74 68 |compilin|g.X   th|
|00002f50| 65 20 63 6f 6d 70 61 72 | 69 73 6f 6e 20 66 75 6e |e compar|ison fun|
|00002f60| 63 74 69 6f 6e 2e 20 20 | 54 68 69 73 20 63 61 6e |ction.  |This can|
|00002f70| 20 72 65 73 75 6c 74 20 | 69 6e 20 61 20 73 75 72 | result |in a sur|
|00002f80| 70 72 69 73 69 6e 67 20 | 0a 58 20 20 20 69 6d 70 |prising |.X   imp|
|00002f90| 72 6f 76 65 6d 65 6e 74 | 20 69 6e 20 70 65 72 66 |rovement| in perf|
|00002fa0| 6f 72 6d 61 6e 63 65 2e | 0a 58 0a 58 33 2e 20 48 |ormance.|.X.X3. H|
|00002fb0| 61 6e 64 20 6f 70 74 69 | 6d 69 7a 65 20 74 68 65 |and opti|mize the|
|00002fc0| 20 63 6f 6d 70 61 72 69 | 73 6f 6e 20 66 75 6e 63 | compari|son func|
|00002fd0| 74 69 6f 6e 2e 20 20 43 | 6f 6e 73 69 64 65 72 20 |tion.  C|onsider |
|00002fe0| 73 6f 72 74 69 6e 67 20 | 6f 6e 0a 58 20 20 20 61 |sorting |on.X   a|
|00002ff0| 20 22 70 72 65 64 69 67 | 65 73 74 65 64 22 20 6b | "predig|ested" k|
|00003000| 65 79 20 74 68 61 74 20 | 72 65 71 75 69 72 65 73 |ey that |requires|
|00003010| 20 6c 65 73 73 20 77 6f | 72 6b 20 74 6f 20 63 6f | less wo|rk to co|
|00003020| 6d 70 61 72 65 20 74 68 | 61 6e 20 0a 58 20 20 20 |mpare th|an .X   |
|00003030| 74 68 65 20 72 65 63 6f | 72 64 73 20 74 68 65 6d |the reco|rds them|
|00003040| 73 65 6c 76 65 73 2e 20 | 20 4d 61 6b 65 20 61 73 |selves. | Make as|
|00003050| 20 66 65 77 20 63 61 6c | 6c 73 20 74 6f 20 6f 74 | few cal|ls to ot|
|00003060| 68 65 72 20 66 75 6e 63 | 74 69 6f 6e 73 20 0a 58 |her func|tions .X|
|00003070| 20 20 20 61 73 20 6e 65 | 63 65 73 73 61 72 79 20 |   as ne|cessary |
|00003080| 66 72 6f 6d 20 77 69 74 | 68 69 6e 20 74 68 65 20 |from wit|hin the |
|00003090| 63 6f 6d 70 61 72 69 73 | 6f 6e 20 66 75 6e 63 74 |comparis|on funct|
|000030a0| 69 6f 6e 2e 0a 58 0a 58 | 34 2e 20 52 65 64 75 63 |ion..X.X|4. Reduc|
|000030b0| 65 20 74 68 65 20 73 69 | 7a 65 20 6f 66 20 74 68 |e the si|ze of th|
|000030c0| 65 20 69 74 65 6d 73 20 | 62 65 69 6e 67 20 73 6f |e items |being so|
|000030d0| 72 74 65 64 2e 20 20 43 | 72 65 61 74 65 20 61 6e |rted.  C|reate an|
|000030e0| 0a 58 20 20 20 61 72 72 | 61 79 20 6f 66 20 70 6f |.X   arr|ay of po|
|000030f0| 69 6e 74 65 72 73 20 74 | 6f 20 72 65 63 6f 72 64 |inters t|o record|
|00003100| 73 20 61 6c 72 65 61 64 | 79 20 65 78 69 73 74 69 |s alread|y existi|
|00003110| 6e 67 20 65 6c 73 65 77 | 68 65 72 65 0a 58 20 20 |ng elsew|here.X  |
|00003120| 20 69 6e 20 6d 65 6d 6f | 72 79 3b 20 74 68 65 20 | in memo|ry; the |
|00003130| 73 6f 72 74 20 77 69 6c | 6c 20 74 68 65 6e 20 6f |sort wil|l then o|
|00003140| 6e 6c 79 20 68 61 76 65 | 20 74 6f 20 73 68 75 66 |nly have| to shuf|
|00003150| 66 6c 65 20 74 68 65 0a | 58 20 20 20 70 6f 69 6e |fle the.|X   poin|
|00003160| 74 65 72 73 20 61 72 6f | 75 6e 64 20 72 61 74 68 |ters aro|und rath|
|00003170| 65 72 20 74 68 61 6e 20 | 63 6f 70 79 20 65 6e 74 |er than |copy ent|
|00003180| 69 72 65 20 72 65 63 6f | 72 64 73 2e 20 20 57 6f |ire reco|rds.  Wo|
|00003190| 72 6b 73 0a 58 20 20 20 | 77 65 6c 6c 20 69 6e 20 |rks.X   |well in |
|000031a0| 63 6f 6d 62 69 6e 61 74 | 69 6f 6e 20 77 69 74 68 |combinat|ion with|
|000031b0| 20 23 33 2e 0a 58 0a 58 | 35 2e 20 43 6f 6e 73 69 | #3..X.X|5. Consi|
|000031c0| 64 65 72 20 6d 61 69 6e | 74 61 69 6e 69 6e 67 20 |der main|taining |
|000031d0| 61 20 62 2d 74 72 65 65 | 20 6f 72 20 6f 74 68 65 |a b-tree| or othe|
|000031e0| 72 20 69 6e 64 65 78 20 | 77 68 69 63 68 0a 58 20 |r index |which.X |
|000031f0| 20 20 6c 61 73 74 73 20 | 62 65 79 6f 6e 64 20 70 |  lasts |beyond p|
|00003200| 72 6f 67 72 61 6d 20 74 | 65 72 6d 69 6e 61 74 69 |rogram t|erminati|
|00003210| 6f 6e 2e 20 20 49 66 20 | 74 68 65 20 69 6e 64 65 |on.  If |the inde|
|00003220| 78 20 69 73 20 75 70 64 | 61 74 65 64 0a 58 20 20 |x is upd|ated.X  |
|00003230| 20 69 6e 66 72 65 71 75 | 65 6e 74 6c 79 20 61 6e | infrequ|ently an|
|00003240| 64 20 6f 6e 6c 79 20 6f | 6e 65 20 6f 72 20 74 77 |d only o|ne or tw|
|00003250| 6f 20 65 6c 65 6d 65 6e | 74 73 20 61 72 65 20 61 |o elemen|ts are a|
|00003260| 64 64 65 64 0a 58 20 20 | 20 74 6f 20 69 74 20 61 |dded.X  | to it a|
|00003270| 74 20 61 20 74 69 6d 65 | 2c 20 74 68 65 20 6d 75 |t a time|, the mu|
|00003280| 63 68 2d 6d 61 6c 69 67 | 6e 65 64 20 62 75 62 62 |ch-malig|ned bubb|
|00003290| 6c 65 20 73 6f 72 74 20 | 6d 69 67 68 74 0a 58 20 |le sort |might.X |
|000032a0| 20 20 61 63 74 75 61 6c | 6c 79 20 62 65 20 6f 66 |  actual|ly be of|
|000032b0| 20 75 73 65 2e 0a 58 0a | 58 36 2e 20 50 6c 75 67 | use..X.|X6. Plug|
|000032c0| 20 69 6e 20 6d 65 72 67 | 65 5f 73 6f 72 74 20 66 | in merg|e_sort f|
|000032d0| 72 6f 6d 20 74 68 69 73 | 20 70 61 63 6b 61 67 65 |rom this| package|
|000032e0| 2e 20 20 45 78 70 65 63 | 74 20 6f 6e 6c 79 20 61 |.  Expec|t only a|
|000032f0| 20 73 6c 69 67 68 74 0a | 58 20 20 20 69 6d 70 72 | slight.|X   impr|
|00003300| 6f 76 65 6d 65 6e 74 2e | 20 20 42 75 74 20 61 20 |ovement.|  But a |
|00003310| 64 65 67 72 61 64 61 74 | 69 6f 6e 20 69 73 20 70 |degradat|ion is p|
|00003320| 6f 73 73 69 62 6c 65 20 | 61 73 20 77 65 6c 6c 3a |ossible |as well:|
|00003330| 20 74 68 69 73 20 6d 65 | 72 67 65 0a 58 20 20 20 | this me|rge.X   |
|00003340| 73 6f 72 74 20 61 6c 6c | 6f 63 61 74 65 73 20 61 |sort all|ocates a|
|00003350| 20 62 69 67 20 63 68 75 | 6e 6b 20 6f 66 20 6d 65 | big chu|nk of me|
|00003360| 6d 6f 72 79 2c 20 77 68 | 69 63 68 20 63 61 6e 20 |mory, wh|ich can |
|00003370| 65 61 74 20 75 70 20 73 | 77 61 70 20 0a 58 20 20 |eat up s|wap .X  |
|00003380| 20 73 70 61 63 65 20 61 | 6e 64 20 73 6c 6f 77 20 | space a|nd slow |
|00003390| 74 68 69 6e 67 73 20 64 | 6f 77 6e 2e 0a 58 0a 58 |things d|own..X.X|
|000033a0| 37 2e 20 4d 61 6b 65 20 | 61 20 63 6f 70 79 20 6f |7. Make |a copy o|
|000033b0| 66 20 74 68 65 20 6d 65 | 72 67 65 5f 73 6f 72 74 |f the me|rge_sort|
|000033c0| 20 63 6f 64 65 20 61 6e | 64 20 72 65 70 6c 61 63 | code an|d replac|
|000033d0| 65 20 74 68 65 20 63 61 | 6c 6c 73 0a 58 20 20 20 |e the ca|lls.X   |
|000033e0| 74 6f 20 74 68 65 20 63 | 6d 70 72 5f 66 75 6e 63 |to the c|mpr_func|
|000033f0| 20 77 69 74 68 20 74 68 | 65 20 61 63 74 75 61 6c | with th|e actual|
|00003400| 20 63 6f 64 65 20 6f 66 | 20 74 68 65 20 63 6f 6d | code of| the com|
|00003410| 70 61 72 65 2e 0a 58 20 | 20 20 4f 72 20 69 66 20 |pare..X |  Or if |
|00003420| 79 6f 75 20 68 61 76 65 | 20 67 63 63 2c 20 74 61 |you have| gcc, ta|
|00003430| 6b 65 20 61 64 76 61 6e | 74 61 67 65 20 6f 66 20 |ke advan|tage of |
|00003440| 69 6e 6c 69 6e 69 6e 67 | 20 74 6f 20 61 63 68 69 |inlining| to achi|
|00003450| 65 76 65 0a 58 20 20 20 | 74 68 65 20 73 61 6d 65 |eve.X   |the same|
|00003460| 20 74 68 69 6e 67 2e 20 | 20 45 78 70 65 63 74 20 | thing. | Expect |
|00003470| 61 6e 20 65 76 65 6e 20 | 6c 65 73 73 20 6e 6f 74 |an even |less not|
|00003480| 69 63 65 61 62 6c 65 20 | 69 6d 70 72 6f 76 65 6d |iceable |improvem|
|00003490| 65 6e 74 2e 0a 58 0a 58 | 38 2e 20 49 66 20 69 74 |ent..X.X|8. If it|
|000034a0| 27 73 20 2a 73 74 69 6c | 6c 20 74 6f 6f 20 73 6c |'s *stil|l too sl|
|000034b0| 6f 77 2a 2c 20 77 72 69 | 74 65 20 61 20 73 6f 72 |ow*, wri|te a sor|
|000034c0| 74 20 74 68 61 74 20 74 | 61 6b 65 73 20 61 64 76 |t that t|akes adv|
|000034d0| 61 6e 74 61 67 65 0a 58 | 20 20 20 6f 66 20 74 68 |antage.X|   of th|
|000034e0| 65 20 64 69 73 74 72 69 | 62 75 74 69 6f 6e 20 6f |e distri|bution o|
|000034f0| 66 20 6b 65 79 73 20 74 | 6f 20 63 61 6c 63 75 6c |f keys t|o calcul|
|00003500| 61 74 65 20 74 68 65 20 | 70 6f 73 69 74 69 6f 6e |ate the |position|
|00003510| 20 6f 66 20 61 0a 58 20 | 20 20 72 65 63 6f 72 64 | of a.X |  record|
|00003520| 20 64 69 72 65 63 74 6c | 79 20 77 69 74 68 6f 75 | directl|y withou|
|00003530| 74 20 68 61 76 69 6e 67 | 20 74 6f 20 63 6f 6d 70 |t having| to comp|
|00003540| 61 72 65 20 69 74 20 74 | 6f 20 6f 74 68 65 72 20 |are it t|o other |
|00003550| 72 65 63 6f 72 64 73 2e | 0a 58 0a 58 0a 58 54 68 |records.|.X.X.XTh|
|00003560| 65 20 63 6f 6d 70 2e 6c | 61 6e 67 2e 63 20 46 41 |e comp.l|ang.c FA|
|00003570| 51 20 6c 69 73 74 20 68 | 61 73 20 74 68 69 73 20 |Q list h|as this |
|00003580| 74 6f 20 73 61 79 20 61 | 62 6f 75 74 20 74 68 65 |to say a|bout the|
|00003590| 20 73 75 62 6a 65 63 74 | 20 6f 66 0a 58 65 66 66 | subject| of.Xeff|
|000035a0| 69 63 69 65 6e 63 79 20 | 69 6e 20 67 65 6e 65 72 |iciency |in gener|
|000035b0| 61 6c 2e 20 20 22 52 65 | 61 64 20 69 74 2e 20 20 |al.  "Re|ad it.  |
|000035c0| 4c 65 61 72 6e 20 69 74 | 2e 20 20 4c 69 76 65 20 |Learn it|.  Live |
|000035d0| 69 74 2e 22 0a 58 0a 58 | 2d 2d 2d 2d 2d 2d 2d 2d |it.".X.X|--------|
|000035e0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000035f0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00003600| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00003610| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00003620| 2d 2d 2d 0a 58 31 37 2e | 31 33 3a 20 20 48 6f 77 |---.X17.|13:  How|
|00003630| 20 63 61 6e 20 49 20 6d | 61 6b 65 20 74 68 69 73 | can I m|ake this|
|00003640| 20 63 6f 64 65 20 6d 6f | 72 65 20 65 66 66 69 63 | code mo|re effic|
|00003650| 69 65 6e 74 3f 0a 58 0a | 58 41 3a 20 20 20 20 20 |ient?.X.|XA:     |
|00003660| 20 45 66 66 69 63 69 65 | 6e 63 79 2c 20 74 68 6f | Efficie|ncy, tho|
|00003670| 75 67 68 20 61 20 66 61 | 76 6f 72 69 74 65 20 63 |ugh a fa|vorite c|
|00003680| 6f 6d 70 2e 6c 61 6e 67 | 2e 63 20 74 6f 70 69 63 |omp.lang|.c topic|
|00003690| 2c 20 69 73 20 6e 6f 74 | 0a 58 20 20 20 20 20 20 |, is not|.X      |
|000036a0| 20 20 69 6d 70 6f 72 74 | 61 6e 74 20 6e 65 61 72 |  import|ant near|
|000036b0| 6c 79 20 61 73 20 6f 66 | 74 65 6e 20 61 73 20 70 |ly as of|ten as p|
|000036c0| 65 6f 70 6c 65 20 74 65 | 6e 64 20 74 6f 20 74 68 |eople te|nd to th|
|000036d0| 69 6e 6b 20 69 74 20 69 | 73 2e 20 20 4d 6f 73 74 |ink it i|s.  Most|
|000036e0| 0a 58 20 20 20 20 20 20 | 20 20 6f 66 20 74 68 65 |.X      |  of the|
|000036f0| 20 63 6f 64 65 20 69 6e | 20 6d 6f 73 74 20 70 72 | code in| most pr|
|00003700| 6f 67 72 61 6d 73 20 69 | 73 20 6e 6f 74 20 74 69 |ograms i|s not ti|
|00003710| 6d 65 2d 63 72 69 74 69 | 63 61 6c 2e 20 20 57 68 |me-criti|cal.  Wh|
|00003720| 65 6e 20 63 6f 64 65 20 | 69 73 0a 58 20 20 20 20 |en code |is.X    |
|00003730| 20 20 20 20 6e 6f 74 20 | 74 69 6d 65 2d 63 72 69 |    not |time-cri|
|00003740| 74 69 63 61 6c 2c 20 69 | 74 20 69 73 20 66 61 72 |tical, i|t is far|
|00003750| 20 6d 6f 72 65 20 69 6d | 70 6f 72 74 61 6e 74 20 | more im|portant |
|00003760| 74 68 61 74 20 69 74 20 | 62 65 20 77 72 69 74 74 |that it |be writt|
|00003770| 65 6e 0a 58 20 20 20 20 | 20 20 20 20 63 6c 65 61 |en.X    |    clea|
|00003780| 72 6c 79 20 61 6e 64 20 | 70 6f 72 74 61 62 6c 79 |rly and |portably|
|00003790| 20 74 68 61 6e 20 74 68 | 61 74 20 69 74 20 62 65 | than th|at it be|
|000037a0| 20 77 72 69 74 74 65 6e | 20 6d 61 78 69 6d 61 6c | written| maximal|
|000037b0| 6c 79 0a 58 20 20 20 20 | 20 20 20 20 65 66 66 69 |ly.X    |    effi|
|000037c0| 63 69 65 6e 74 6c 79 2e | 20 20 28 52 65 6d 65 6d |ciently.|  (Remem|
|000037d0| 62 65 72 20 74 68 61 74 | 20 63 6f 6d 70 75 74 65 |ber that| compute|
|000037e0| 72 73 20 61 72 65 20 76 | 65 72 79 2c 20 76 65 72 |rs are v|ery, ver|
|000037f0| 79 20 66 61 73 74 2c 20 | 61 6e 64 0a 58 20 20 20 |y fast, |and.X   |
|00003800| 20 20 20 20 20 74 68 61 | 74 20 65 76 65 6e 20 22 |     tha|t even "|
|00003810| 69 6e 65 66 66 69 63 69 | 65 6e 74 22 20 63 6f 64 |ineffici|ent" cod|
|00003820| 65 20 63 61 6e 20 72 75 | 6e 20 77 69 74 68 6f 75 |e can ru|n withou|
|00003830| 74 20 61 70 70 61 72 65 | 6e 74 20 64 65 6c 61 79 |t appare|nt delay|
|00003840| 2e 29 0a 58 0a 58 20 20 | 20 20 20 20 20 20 49 74 |.).X.X  |      It|
|00003850| 20 69 73 20 6e 6f 74 6f | 72 69 6f 75 73 6c 79 20 | is noto|riously |
|00003860| 64 69 66 66 69 63 75 6c | 74 20 74 6f 20 70 72 65 |difficul|t to pre|
|00003870| 64 69 63 74 20 77 68 61 | 74 20 74 68 65 20 22 68 |dict wha|t the "h|
|00003880| 6f 74 20 73 70 6f 74 73 | 22 20 69 6e 20 61 0a 58 |ot spots|" in a.X|
|00003890| 20 20 20 20 20 20 20 20 | 70 72 6f 67 72 61 6d 20 |        |program |
|000038a0| 77 69 6c 6c 20 62 65 2e | 20 20 57 68 65 6e 20 65 |will be.|  When e|
|000038b0| 66 66 69 63 69 65 6e 63 | 79 20 69 73 20 61 20 63 |fficienc|y is a c|
|000038c0| 6f 6e 63 65 72 6e 2c 20 | 69 74 20 69 73 20 69 6d |oncern, |it is im|
|000038d0| 70 6f 72 74 61 6e 74 0a | 58 20 20 20 20 20 20 20 |portant.|X       |
|000038e0| 20 74 6f 20 75 73 65 20 | 70 72 6f 66 69 6c 69 6e | to use |profilin|
|000038f0| 67 20 73 6f 66 74 77 61 | 72 65 20 74 6f 20 64 65 |g softwa|re to de|
|00003900| 74 65 72 6d 69 6e 65 20 | 77 68 69 63 68 20 70 61 |termine |which pa|
|00003910| 72 74 73 20 6f 66 20 74 | 68 65 0a 58 20 20 20 20 |rts of t|he.X    |
|00003920| 20 20 20 20 70 72 6f 67 | 72 61 6d 20 64 65 73 65 |    prog|ram dese|
|00003930| 72 76 65 20 61 74 74 65 | 6e 74 69 6f 6e 2e 20 20 |rve atte|ntion.  |
|00003940| 4f 66 74 65 6e 2c 20 61 | 63 74 75 61 6c 20 63 6f |Often, a|ctual co|
|00003950| 6d 70 75 74 61 74 69 6f | 6e 20 74 69 6d 65 20 69 |mputatio|n time i|
|00003960| 73 0a 58 20 20 20 20 20 | 20 20 20 73 77 61 6d 70 |s.X     |   swamp|
|00003970| 65 64 20 62 79 20 70 65 | 72 69 70 68 65 72 61 6c |ed by pe|ripheral|
|00003980| 20 74 61 73 6b 73 20 73 | 75 63 68 20 61 73 20 49 | tasks s|uch as I|
|00003990| 2f 4f 20 61 6e 64 20 6d | 65 6d 6f 72 79 20 61 6c |/O and m|emory al|
|000039a0| 6c 6f 63 61 74 69 6f 6e | 2c 0a 58 20 20 20 20 20 |location|,.X     |
|000039b0| 20 20 20 77 68 69 63 68 | 20 63 61 6e 20 62 65 20 |   which| can be |
|000039c0| 73 70 65 64 20 75 70 20 | 62 79 20 75 73 69 6e 67 |sped up |by using|
|000039d0| 20 62 75 66 66 65 72 69 | 6e 67 20 61 6e 64 20 63 | bufferi|ng and c|
|000039e0| 61 63 68 65 69 6e 67 20 | 74 65 63 68 6e 69 71 75 |acheing |techniqu|
|000039f0| 65 73 2e 0a 58 0a 58 20 | 20 20 20 20 20 20 20 46 |es..X.X |       F|
|00003a00| 6f 72 20 74 68 65 20 73 | 6d 61 6c 6c 20 66 72 61 |or the s|mall fra|
|00003a10| 63 74 69 6f 6e 20 6f 66 | 20 63 6f 64 65 20 74 68 |ction of| code th|
|00003a20| 61 74 20 69 73 20 74 69 | 6d 65 2d 63 72 69 74 69 |at is ti|me-criti|
|00003a30| 63 61 6c 2c 20 69 74 20 | 69 73 0a 58 20 20 20 20 |cal, it |is.X    |
|00003a40| 20 20 20 20 76 69 74 61 | 6c 20 74 6f 20 70 69 63 |    vita|l to pic|
|00003a50| 6b 20 61 20 67 6f 6f 64 | 20 61 6c 67 6f 72 69 74 |k a good| algorit|
|00003a60| 68 6d 3b 20 69 74 20 69 | 73 20 6c 65 73 73 20 69 |hm; it i|s less i|
|00003a70| 6d 70 6f 72 74 61 6e 74 | 20 74 6f 0a 58 20 20 20 |mportant| to.X   |
|00003a80| 20 20 20 20 20 22 6d 69 | 63 72 6f 6f 70 74 69 6d |     "mi|crooptim|
|00003a90| 69 7a 65 22 20 74 68 65 | 20 63 6f 64 69 6e 67 20 |ize" the| coding |
|00003aa0| 64 65 74 61 69 6c 73 2e | 20 20 4d 61 6e 79 20 6f |details.|  Many o|
|00003ab0| 66 20 74 68 65 20 22 65 | 66 66 69 63 69 65 6e 74 |f the "e|fficient|
|00003ac0| 0a 58 20 20 20 20 20 20 | 20 20 63 6f 64 69 6e 67 |.X      |  coding|
|00003ad0| 20 74 72 69 63 6b 73 22 | 20 77 68 69 63 68 20 61 | tricks"| which a|
|00003ae0| 72 65 20 66 72 65 71 75 | 65 6e 74 6c 79 20 73 75 |re frequ|ently su|
|00003af0| 67 67 65 73 74 65 64 20 | 28 65 2e 67 2e 20 73 75 |ggested |(e.g. su|
|00003b00| 62 73 74 69 74 75 74 69 | 6e 67 0a 58 20 20 20 20 |bstituti|ng.X    |
|00003b10| 20 20 20 20 73 68 69 66 | 74 20 6f 70 65 72 61 74 |    shif|t operat|
|00003b20| 6f 72 73 20 66 6f 72 20 | 6d 75 6c 74 69 70 6c 69 |ors for |multipli|
|00003b30| 63 61 74 69 6f 6e 20 62 | 79 20 70 6f 77 65 72 73 |cation b|y powers|
|00003b40| 20 6f 66 20 74 77 6f 29 | 20 61 72 65 0a 58 20 20 | of two)| are.X  |
|00003b50| 20 20 20 20 20 20 70 65 | 72 66 6f 72 6d 65 64 20 |      pe|rformed |
|00003b60| 61 75 74 6f 6d 61 74 69 | 63 61 6c 6c 79 20 62 79 |automati|cally by|
|00003b70| 20 65 76 65 6e 20 73 69 | 6d 70 6c 65 6d 69 6e 64 | even si|mplemind|
|00003b80| 65 64 20 63 6f 6d 70 69 | 6c 65 72 73 2e 0a 58 20 |ed compi|lers..X |
|00003b90| 20 20 20 20 20 20 20 48 | 65 61 76 79 68 61 6e 64 |       H|eavyhand|
|00003ba0| 65 64 20 22 6f 70 74 69 | 6d 69 7a 61 74 69 6f 6e |ed "opti|mization|
|00003bb0| 22 20 61 74 74 65 6d 70 | 74 73 20 63 61 6e 20 6d |" attemp|ts can m|
|00003bc0| 61 6b 65 20 63 6f 64 65 | 20 73 6f 20 62 75 6c 6b |ake code| so bulk|
|00003bd0| 79 20 74 68 61 74 0a 58 | 20 20 20 20 20 20 20 20 |y that.X|        |
|00003be0| 70 65 72 66 6f 72 6d 61 | 6e 63 65 20 69 73 20 64 |performa|nce is d|
|00003bf0| 65 67 72 61 64 65 64 2e | 0a 58 0a 58 20 20 20 20 |egraded.|.X.X    |
|00003c00| 20 20 20 20 46 6f 72 20 | 6d 6f 72 65 20 64 69 73 |    For |more dis|
|00003c10| 63 75 73 73 69 6f 6e 20 | 6f 66 20 65 66 66 69 63 |cussion |of effic|
|00003c20| 69 65 6e 63 79 20 74 72 | 61 64 65 6f 66 66 73 2c |iency tr|adeoffs,|
|00003c30| 20 61 73 20 77 65 6c 6c | 20 61 73 20 67 6f 6f 64 | as well| as good|
|00003c40| 0a 58 20 20 20 20 20 20 | 20 20 61 64 76 69 63 65 |.X      |  advice|
|00003c50| 20 6f 6e 20 68 6f 77 20 | 74 6f 20 69 6e 63 72 65 | on how |to incre|
|00003c60| 61 73 65 20 65 66 66 69 | 63 69 65 6e 63 79 20 77 |ase effi|ciency w|
|00003c70| 68 65 6e 20 69 74 20 69 | 73 20 69 6d 70 6f 72 74 |hen it i|s import|
|00003c80| 61 6e 74 2c 20 73 65 65 | 0a 58 20 20 20 20 20 20 |ant, see|.X      |
|00003c90| 20 20 63 68 61 70 74 65 | 72 20 37 20 6f 66 20 4b |  chapte|r 7 of K|
|00003ca0| 65 72 6e 69 67 68 61 6e | 20 61 6e 64 20 50 6c 61 |ernighan| and Pla|
|00003cb0| 75 67 65 72 27 73 20 54 | 68 65 20 45 6c 65 6d 65 |uger's T|he Eleme|
|00003cc0| 6e 74 73 20 6f 66 20 50 | 72 6f 67 72 61 6d 6d 69 |nts of P|rogrammi|
|00003cd0| 6e 67 0a 58 20 20 20 20 | 20 20 20 20 53 74 79 6c |ng.X    |    Styl|
|00003ce0| 65 2c 20 61 6e 64 20 4a | 6f 6e 20 42 65 6e 74 6c |e, and J|on Bentl|
|00003cf0| 65 79 27 73 20 57 72 69 | 74 69 6e 67 20 45 66 66 |ey's Wri|ting Eff|
|00003d00| 69 63 69 65 6e 74 20 50 | 72 6f 67 72 61 6d 73 2e |icient P|rograms.|
|00003d10| 0a 58 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |.X------|--------|
|00003d20| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00003d30| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00003d40| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00003d50| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 0a 58 0a |--------|-----.X.|
|00003d60| 45 4e 44 5f 4f 46 5f 46 | 49 4c 45 0a 20 20 69 66 |END_OF_F|ILE.  if|
|00003d70| 20 74 65 73 74 20 34 34 | 35 32 20 2d 6e 65 20 60 | test 44|52 -ne `|
|00003d80| 77 63 20 2d 63 20 3c 27 | 4f 50 54 49 4d 49 5a 49 |wc -c <'|OPTIMIZI|
|00003d90| 4e 47 27 60 3b 20 74 68 | 65 6e 0a 20 20 20 20 65 |NG'`; th|en.    e|
|00003da0| 63 68 6f 20 73 68 61 72 | 3a 20 5c 22 27 4f 50 54 |cho shar|: \"'OPT|
|00003db0| 49 4d 49 5a 49 4e 47 27 | 5c 22 20 75 6e 70 61 63 |IMIZING'|\" unpac|
|00003dc0| 6b 65 64 20 77 69 74 68 | 20 77 72 6f 6e 67 20 73 |ked with| wrong s|
|00003dd0| 69 7a 65 21 0a 20 20 66 | 69 0a 20 20 23 20 65 6e |ize!.  f|i.  # en|
|00003de0| 64 20 6f 66 20 27 4f 50 | 54 49 4d 49 5a 49 4e 47 |d of 'OP|TIMIZING|
|00003df0| 27 0a 66 69 0a 69 66 20 | 74 65 73 74 20 2d 66 20 |'.fi.if |test -f |
|00003e00| 27 54 4f 44 4f 27 20 2d | 61 20 22 24 7b 31 7d 22 |'TODO' -|a "${1}"|
|00003e10| 20 21 3d 20 22 2d 63 22 | 20 3b 20 74 68 65 6e 20 | != "-c"| ; then |
|00003e20| 0a 20 20 65 63 68 6f 20 | 73 68 61 72 3a 20 57 69 |.  echo |shar: Wi|
|00003e30| 6c 6c 20 6e 6f 74 20 63 | 6c 6f 62 62 65 72 20 65 |ll not c|lobber e|
|00003e40| 78 69 73 74 69 6e 67 20 | 66 69 6c 65 20 5c 22 27 |xisting |file \"'|
|00003e50| 54 4f 44 4f 27 5c 22 0a | 65 6c 73 65 0a 20 20 65 |TODO'\".|else.  e|
|00003e60| 63 68 6f 20 73 68 61 72 | 3a 20 45 78 74 72 61 63 |cho shar|: Extrac|
|00003e70| 74 69 6e 67 20 5c 22 27 | 54 4f 44 4f 27 5c 22 20 |ting \"'|TODO'\" |
|00003e80| 5c 28 39 33 35 20 63 68 | 61 72 61 63 74 65 72 73 |\(935 ch|aracters|
|00003e90| 5c 29 0a 20 20 73 65 64 | 20 22 73 2f 5e 58 2f 2f |\).  sed| "s/^X//|
|00003ea0| 22 20 3e 27 54 4f 44 4f | 27 20 3c 3c 27 45 4e 44 |" >'TODO|' <<'END|
|00003eb0| 5f 4f 46 5f 46 49 4c 45 | 27 0a 58 0a 58 72 65 74 |_OF_FILE|'.X.Xret|
|00003ec0| 75 72 6e 20 2d 31 20 6f | 72 20 73 6f 6d 65 74 68 |urn -1 o|r someth|
|00003ed0| 69 6e 67 20 72 61 74 68 | 65 72 20 74 68 61 6e 20 |ing rath|er than |
|00003ee0| 63 61 6c 6c 69 6e 67 20 | 61 73 73 65 72 74 28 29 |calling |assert()|
|00003ef0| 20 69 6e 20 6d 61 6e 79 | 20 70 6c 61 63 65 73 0a | in many| places.|
|00003f00| 58 0a 58 75 73 65 20 22 | 74 61 67 22 20 73 6f 72 |X.Xuse "|tag" sor|
|00003f10| 74 20 77 68 65 6e 20 73 | 69 7a 65 20 6f 66 20 72 |t when s|ize of r|
|00003f20| 65 63 6f 72 64 73 20 69 | 73 20 73 6f 20 6c 61 72 |ecords i|s so lar|
|00003f30| 67 65 20 0a 58 20 20 74 | 68 61 74 20 6d 65 6d 63 |ge .X  t|hat memc|
|00003f40| 70 79 20 74 61 6b 65 73 | 20 61 20 73 69 67 6e 69 |py takes| a signi|
|00003f50| 66 69 63 61 6e 74 20 61 | 6d 6f 75 6e 74 20 6f 66 |ficant a|mount of|
|00003f60| 20 74 69 6d 65 2e 0a 58 | 0a 58 62 65 74 74 65 72 | time..X|.Xbetter|
|00003f70| 20 66 6c 6f 77 20 63 6f | 6e 74 72 6f 6c 20 69 6e | flow co|ntrol in|
|00003f80| 20 66 6c 6f 67 67 65 72 | 3b 20 61 64 64 20 73 6f | flogger|; add so|
|00003f90| 6d 65 20 63 6f 6d 6d 61 | 6e 64 20 6c 69 6e 65 20 |me comma|nd line |
|00003fa0| 6f 70 74 69 6f 6e 73 0a | 58 20 20 66 6f 72 20 73 |options.|X  for s|
|00003fb0| 65 6c 65 63 74 69 6e 67 | 20 77 68 69 63 68 20 61 |electing| which a|
|00003fc0| 6c 67 6f 72 69 74 68 6d | 73 20 74 6f 20 74 65 73 |lgorithm|s to tes|
|00003fd0| 74 20 61 6e 64 20 77 68 | 69 63 68 20 73 69 74 75 |t and wh|ich situ|
|00003fe0| 61 74 69 6f 6e 73 0a 58 | 20 20 74 6f 20 70 72 65 |ations.X|  to pre|
|00003ff0| 73 65 6e 74 20 74 68 65 | 6d 20 77 69 74 68 2e 0a |sent the|m with..|
|00004000| 58 0a 58 74 68 65 20 63 | 68 65 63 6b 20 66 6f 72 |X.Xthe c|heck for|
|00004010| 20 73 74 61 62 6c 65 20 | 73 6f 72 74 69 6e 67 20 | stable |sorting |
|00004020| 69 73 6e 27 74 20 64 65 | 63 69 73 69 76 65 2e 0a |isn't de|cisive..|
|00004030| 58 0a 58 73 6f 6d 65 20 | 6f 66 20 74 68 65 20 66 |X.Xsome |of the f|
|00004040| 69 6c 65 20 6e 61 6d 65 | 73 20 65 78 63 65 65 64 |ile name|s exceed|
|00004050| 20 31 34 20 63 68 61 72 | 61 63 74 65 72 73 0a 58 | 14 char|acters.X|
|00004060| 0a 58 6d 61 6b 65 20 74 | 68 65 20 61 6c 69 67 6e |.Xmake t|he align|
|00004070| 6d 65 6e 74 20 63 68 65 | 63 6b 69 6e 67 20 65 61 |ment che|cking ea|
|00004080| 73 69 65 72 20 74 6f 20 | 63 6f 6e 66 69 67 75 72 |sier to |configur|
|00004090| 65 20 28 6d 65 72 67 65 | 20 61 6e 64 20 71 75 69 |e (merge| and qui|
|000040a0| 63 6b 20 73 6f 72 74 73 | 29 0a 58 0a 58 6d 61 79 |ck sorts|).X.Xmay|
|000040b0| 62 65 20 61 6e 61 6c 79 | 7a 65 20 69 6e 63 72 65 |be analy|ze incre|
|000040c0| 61 73 65 20 69 6e 20 73 | 70 61 63 65 2f 74 69 6d |ase in s|pace/tim|
|000040d0| 65 20 63 6f 6d 70 6c 65 | 78 69 74 79 20 61 73 20 |e comple|xity as |
|000040e0| 61 72 72 61 79 20 73 69 | 7a 65 20 67 72 6f 77 73 |array si|ze grows|
|000040f0| 0a 58 20 20 61 6e 64 20 | 66 69 67 75 72 65 20 6f |.X  and |figure o|
|00004100| 75 74 20 4f 28 29 20 65 | 6d 70 69 72 69 63 61 6c |ut O() e|mpirical|
|00004110| 6c 79 2e 0a 58 0a 58 69 | 6e 63 6c 75 64 65 20 66 |ly..X.Xi|nclude f|
|00004120| 69 6c 65 20 22 73 6f 72 | 74 69 6e 67 2e 68 22 20 |ile "sor|ting.h" |
|00004130| 69 73 20 6f 66 20 71 75 | 65 73 74 69 6f 6e 61 62 |is of qu|estionab|
|00004140| 6c 65 20 75 74 69 6c 69 | 74 79 2e 0a 58 0a 58 2f |le utili|ty..X.X/|
|00004150| 75 73 72 2f 6c 69 62 2f | 6c 69 6e 74 2f 6c 6c 69 |usr/lib/|lint/lli|
|00004160| 62 2d 6c 73 6f 72 74 20 | 6d 69 67 68 74 20 62 65 |b-lsort |might be|
|00004170| 20 61 20 6e 69 63 65 20 | 74 6f 75 63 68 20 66 6f | a nice |touch fo|
|00004180| 72 20 22 6d 61 6b 65 20 | 69 6e 73 74 61 6c 6c 22 |r "make |install"|
|00004190| 0a 58 0a 58 73 68 6f 75 | 6c 64 20 62 65 20 6d 6f |.X.Xshou|ld be mo|
|000041a0| 72 65 20 66 6c 65 78 69 | 62 6c 65 20 61 62 6f 75 |re flexi|ble abou|
|000041b0| 74 20 77 68 61 74 20 73 | 69 7a 65 20 61 6e 64 20 |t what s|ize and |
|000041c0| 63 6f 6d 70 6c 65 78 69 | 74 79 20 6f 66 20 74 68 |complexi|ty of th|
|000041d0| 69 6e 67 20 74 6f 20 73 | 6f 72 74 0a 58 0a 58 6d |ing to s|ort.X.Xm|
|000041e0| 61 79 62 65 20 61 64 64 | 20 61 20 70 61 72 61 6c |aybe add| a paral|
|000041f0| 6c 65 6c 69 7a 69 6e 67 | 20 73 6f 72 74 0a 58 0a |lelizing| sort.X.|
|00004200| 58 6d 61 6b 65 66 69 6c | 65 20 61 6e 64 20 66 6c |Xmakefil|e and fl|
|00004210| 6f 67 67 65 72 20 61 72 | 65 6e 74 27 74 20 76 65 |ogger ar|ent't ve|
|00004220| 72 79 20 70 6f 72 74 61 | 62 6c 65 0a 58 0a 58 63 |ry porta|ble.X.Xc|
|00004230| 63 20 2d 70 69 63 20 69 | 73 20 75 6e 6e 65 63 65 |c -pic i|s unnece|
|00004240| 73 73 61 72 79 20 77 68 | 65 6e 20 6d 61 6b 69 6e |ssary wh|en makin|
|00004250| 67 20 6c 69 62 73 6f 72 | 74 2e 61 0a 58 0a 58 61 |g libsor|t.a.X.Xa|
|00004260| 64 64 20 74 65 73 74 20 | 66 6f 72 20 72 65 2d 65 |dd test |for re-e|
|00004270| 6e 74 72 61 6e 63 79 20 | 6f 66 20 73 6f 72 74 0a |ntrancy |of sort.|
|00004280| 58 0a 45 4e 44 5f 4f 46 | 5f 46 49 4c 45 0a 20 20 |X.END_OF|_FILE.  |
|00004290| 69 66 20 74 65 73 74 20 | 39 33 35 20 2d 6e 65 20 |if test |935 -ne |
|000042a0| 60 77 63 20 2d 63 20 3c | 27 54 4f 44 4f 27 60 3b |`wc -c <|'TODO'`;|
|000042b0| 20 74 68 65 6e 0a 20 20 | 20 20 65 63 68 6f 20 73 | then.  |  echo s|
|000042c0| 68 61 72 3a 20 5c 22 27 | 54 4f 44 4f 27 5c 22 20 |har: \"'|TODO'\" |
|000042d0| 75 6e 70 61 63 6b 65 64 | 20 77 69 74 68 20 77 72 |unpacked| with wr|
|000042e0| 6f 6e 67 20 73 69 7a 65 | 21 0a 20 20 66 69 0a 20 |ong size|!.  fi. |
|000042f0| 20 23 20 65 6e 64 20 6f | 66 20 27 54 4f 44 4f 27 | # end o|f 'TODO'|
|00004300| 0a 66 69 0a 69 66 20 74 | 65 73 74 20 2d 66 20 27 |.fi.if t|est -f '|
|00004310| 66 6c 6f 67 67 65 72 2e | 63 27 20 2d 61 20 22 24 |flogger.|c' -a "$|
|00004320| 7b 31 7d 22 20 21 3d 20 | 22 2d 63 22 20 3b 20 74 |{1}" != |"-c" ; t|
|00004330| 68 65 6e 20 0a 20 20 65 | 63 68 6f 20 73 68 61 72 |hen .  e|cho shar|
|00004340| 3a 20 57 69 6c 6c 20 6e | 6f 74 20 63 6c 6f 62 62 |: Will n|ot clobb|
|00004350| 65 72 20 65 78 69 73 74 | 69 6e 67 20 66 69 6c 65 |er exist|ing file|
|00004360| 20 5c 22 27 66 6c 6f 67 | 67 65 72 2e 63 27 5c 22 | \"'flog|ger.c'\"|
|00004370| 0a 65 6c 73 65 0a 20 20 | 65 63 68 6f 20 73 68 61 |.else.  |echo sha|
|00004380| 72 3a 20 45 78 74 72 61 | 63 74 69 6e 67 20 5c 22 |r: Extra|cting \"|
|00004390| 27 66 6c 6f 67 67 65 72 | 2e 63 27 5c 22 20 5c 28 |'flogger|.c'\" \(|
|000043a0| 31 36 30 37 35 20 63 68 | 61 72 61 63 74 65 72 73 |16075 ch|aracters|
|000043b0| 5c 29 0a 20 20 73 65 64 | 20 22 73 2f 5e 58 2f 2f |\).  sed| "s/^X//|
|000043c0| 22 20 3e 27 66 6c 6f 67 | 67 65 72 2e 63 27 20 3c |" >'flog|ger.c' <|
|000043d0| 3c 27 45 4e 44 5f 4f 46 | 5f 46 49 4c 45 27 0a 58 |<'END_OF|_FILE'.X|
|000043e0| 0a 58 2f 2a 20 0a 58 0a | 58 4e 41 4d 45 0a 58 20 |.X/* .X.|XNAME.X |
|000043f0| 20 66 6c 6f 67 67 65 72 | 0a 58 0a 58 44 45 53 43 | flogger|.X.XDESC|
|00004400| 52 49 50 54 49 4f 4e 0a | 58 0a 58 20 20 50 75 74 |RIPTION.|X.X  Put|
|00004410| 20 74 68 65 20 73 6f 72 | 74 20 72 6f 75 74 69 6e | the sor|t routin|
|00004420| 65 73 20 74 68 72 6f 75 | 67 68 20 74 68 65 20 70 |es throu|gh the p|
|00004430| 61 63 65 73 2e 20 20 56 | 65 72 69 66 79 20 74 68 |aces.  V|erify th|
|00004440| 61 74 20 74 68 65 79 20 | 61 63 74 75 61 6c 6c 79 |at they |actually|
|00004450| 0a 58 20 20 6f 72 64 65 | 72 20 64 61 74 61 20 70 |.X  orde|r data p|
|00004460| 72 6f 70 65 72 6c 79 20 | 61 6e 64 20 74 68 61 74 |roperly |and that|
|00004470| 20 74 68 65 79 20 64 6f | 6e 27 74 20 6d 6f 6c 65 | they do|n't mole|
|00004480| 73 74 20 74 68 65 20 6d | 65 6d 6f 72 79 20 6c 6f |st the m|emory lo|
|00004490| 63 61 74 69 6f 6e 73 0a | 58 20 20 69 6d 6d 65 64 |cations.|X  immed|
|000044a0| 69 61 74 65 6c 79 20 61 | 62 6f 76 65 20 6f 72 20 |iately a|bove or |
|000044b0| 62 65 6c 6f 77 20 74 68 | 65 20 61 72 72 61 79 2e |below th|e array.|
|000044c0| 20 20 54 72 69 65 73 20 | 73 6f 6d 65 20 63 6f 6d |  Tries |some com|
|000044d0| 6d 6f 6e 20 77 6f 72 73 | 74 2d 63 61 73 65 0a 58 |mon wors|t-case.X|
|000044e0| 20 20 73 69 74 75 61 74 | 69 6f 6e 73 20 6c 69 6b |  situat|ions lik|
|000044f0| 65 20 61 6c 72 65 61 64 | 79 2d 6f 72 64 65 72 65 |e alread|y-ordere|
|00004500| 64 20 64 61 74 61 20 61 | 6e 64 20 63 6f 6d 70 61 |d data a|nd compa|
|00004510| 72 69 73 6f 6e 20 66 75 | 6e 63 74 69 6f 6e 73 20 |rison fu|nctions |
|00004520| 77 68 69 63 68 0a 58 20 | 20 61 72 65 20 64 65 66 |which.X | are def|
|00004530| 65 63 74 69 76 65 2e 0a | 58 0a 58 20 20 50 72 69 |ective..|X.X  Pri|
|00004540| 6e 74 73 20 6f 75 74 20 | 65 73 74 69 6d 61 74 65 |nts out |estimate|
|00004550| 73 20 66 6f 72 20 65 61 | 63 68 20 73 6f 72 74 20 |s for ea|ch sort |
|00004560| 61 6c 67 6f 72 69 74 68 | 6d 20 66 6f 72 20 75 73 |algorith|m for us|
|00004570| 61 67 65 20 6f 66 20 68 | 65 61 70 20 73 70 61 63 |age of h|eap spac|
|00004580| 65 2c 0a 58 20 20 73 74 | 61 63 6b 20 73 70 61 63 |e,.X  st|ack spac|
|00004590| 65 2c 20 61 6e 64 20 72 | 75 6e 20 74 69 6d 65 20 |e, and r|un time |
|000045a0| 61 6e 64 20 61 6c 73 6f | 20 66 6f 72 20 74 68 65 |and also| for the|
|000045b0| 20 6e 75 6d 62 65 72 20 | 6f 66 20 63 61 6c 6c 73 | number |of calls|
|000045c0| 20 74 6f 20 74 68 65 0a | 58 20 20 63 6f 6d 70 61 | to the.|X  compa|
|000045d0| 72 69 73 6f 6e 20 66 75 | 6e 63 74 69 6f 6e 2e 0a |rison fu|nction..|
|000045e0| 58 0a 58 20 20 54 61 6b | 65 73 20 6f 6e 65 20 63 |X.X  Tak|es one c|
|000045f0| 6f 6d 6d 61 6e 64 20 6c | 69 6e 65 20 61 72 67 75 |ommand l|ine argu|
|00004600| 6d 65 6e 74 20 77 68 69 | 63 68 20 73 70 65 63 69 |ment whi|ch speci|
|00004610| 66 69 65 73 20 74 68 65 | 20 6e 75 6d 62 65 72 20 |fies the| number |
|00004620| 6f 66 20 69 74 65 6d 73 | 0a 58 20 20 74 6f 20 70 |of items|.X  to p|
|00004630| 75 74 20 69 6e 20 74 68 | 65 20 61 72 72 61 79 2e |ut in th|e array.|
|00004640| 20 20 4c 61 72 67 65 72 | 20 76 61 6c 75 65 73 20 |  Larger| values |
|00004650| 74 61 6b 65 20 6c 6f 6e | 67 65 72 20 74 6f 20 72 |take lon|ger to r|
|00004660| 75 6e 2e 0a 58 0a 58 41 | 55 54 48 4f 52 53 48 49 |un..X.XA|UTHORSHI|
|00004670| 50 0a 58 0a 58 20 20 4d | 69 6b 65 20 4c 65 65 2c |P.X.X  M|ike Lee,|
|00004680| 20 63 75 72 72 65 6e 74 | 6c 79 20 6d 69 6b 65 79 | current|ly mikey|
|00004690| 40 6f 6e 74 65 6b 2e 63 | 6f 6d 0a 58 0a 58 52 45 |@ontek.c|om.X.XRE|
|000046a0| 46 45 52 45 4e 43 45 53 | 0a 58 0a 58 20 20 4b 6e |FERENCES|.X.X  Kn|
|000046b0| 75 74 68 2c 20 41 72 74 | 20 6f 66 20 43 6f 6d 70 |uth, Art| of Comp|
|000046c0| 75 74 65 72 20 50 72 6f | 67 72 61 6d 6d 69 6e 67 |uter Pro|gramming|
|000046d0| 20 56 6f 6c 20 33 3a 20 | 53 65 61 72 63 68 69 6e | Vol 3: |Searchin|
|000046e0| 67 20 61 6e 64 20 53 6f | 72 74 69 6e 67 0a 58 20 |g and So|rting.X |
|000046f0| 20 4b 65 72 6e 69 67 68 | 61 6e 20 26 20 52 69 63 | Kernigh|an & Ric|
|00004700| 68 74 69 65 2c 20 54 68 | 65 20 43 20 50 72 6f 67 |htie, Th|e C Prog|
|00004710| 72 61 6d 6d 69 6e 67 20 | 4c 61 6e 67 75 61 67 65 |ramming |Language|
|00004720| 2c 20 53 65 63 6f 6e 64 | 20 45 64 69 74 69 6f 6e |, Second| Edition|
|00004730| 0a 58 0a 58 57 4f 52 4b | 20 52 45 4d 41 49 4e 49 |.X.XWORK| REMAINI|
|00004740| 4e 47 0a 58 0a 58 20 20 | 54 68 65 20 6d 61 69 6e |NG.X.X  |The main|
|00004750| 20 6c 6f 6f 70 20 69 73 | 20 68 6f 70 65 6c 65 73 | loop is| hopeles|
|00004760| 73 2e 0a 58 20 20 53 65 | 65 20 74 68 65 20 54 4f |s..X  Se|e the TO|
|00004770| 44 4f 20 64 6f 63 75 6d | 65 6e 74 20 28 77 68 69 |DO docum|ent (whi|
|00004780| 63 68 20 73 68 6f 75 6c | 64 20 61 63 63 6f 6d 70 |ch shoul|d accomp|
|00004790| 61 6e 79 20 74 68 69 73 | 20 70 72 6f 67 72 61 6d |any this| program|
|000047a0| 2e 29 0a 58 0a 58 43 4f | 50 59 52 49 47 48 54 0a |.).X.XCO|PYRIGHT.|
|000047b0| 58 0a 58 20 20 43 6f 70 | 79 72 69 67 68 74 20 31 |X.X  Cop|yright 1|
|000047c0| 39 39 32 20 4d 69 63 68 | 61 65 6c 20 4c 65 65 2e |992 Mich|ael Lee.|
|000047d0| 0a 58 0a 58 20 20 28 31 | 29 20 50 65 72 6d 69 73 |.X.X  (1|) Permis|
|000047e0| 73 69 6f 6e 20 74 6f 20 | 75 73 65 2c 20 63 6f 70 |sion to |use, cop|
|000047f0| 79 2c 20 64 69 73 74 72 | 69 62 75 74 65 2c 20 61 |y, distr|ibute, a|
|00004800| 6e 64 20 6d 61 6b 65 20 | 63 68 61 6e 67 65 73 20 |nd make |changes |
|00004810| 69 73 20 67 72 61 6e 74 | 65 64 0a 58 20 20 70 72 |is grant|ed.X  pr|
|00004820| 6f 76 69 64 69 6e 67 20 | 74 68 61 74 20 28 61 29 |oviding |that (a)|
|00004830| 20 74 68 61 74 20 79 6f | 75 20 64 6f 20 73 6f 20 | that yo|u do so |
|00004840| 77 69 74 68 6f 75 74 20 | 63 68 61 72 67 69 6e 67 |without |charging|
|00004850| 20 61 6e 79 6f 6e 65 20 | 61 20 66 65 65 20 61 6e | anyone |a fee an|
|00004860| 64 0a 58 20 20 28 62 29 | 20 74 68 69 73 20 63 6f |d.X  (b)| this co|
|00004870| 70 79 72 69 67 68 74 20 | 6e 6f 74 69 63 65 20 6d |pyright |notice m|
|00004880| 75 73 74 20 62 65 20 69 | 6e 63 6c 75 64 65 64 20 |ust be i|ncluded |
|00004890| 76 65 72 62 61 74 69 6d | 20 69 6e 20 61 6c 6c 20 |verbatim| in all |
|000048a0| 63 6f 70 69 65 73 20 61 | 6e 64 20 0a 58 20 20 64 |copies a|nd .X  d|
|000048b0| 69 73 74 72 69 62 75 74 | 69 6f 6e 73 2e 20 20 0a |istribut|ions.  .|
|000048c0| 58 0a 58 20 20 28 32 29 | 20 54 68 65 72 65 20 69 |X.X  (2)| There i|
|000048d0| 73 20 6e 6f 20 77 61 72 | 72 61 6e 74 79 20 66 6f |s no war|ranty fo|
|000048e0| 72 20 74 68 69 73 20 70 | 72 6f 67 72 61 6d 2c 20 |r this p|rogram, |
|000048f0| 74 6f 20 74 68 65 20 65 | 78 74 65 6e 74 20 70 65 |to the e|xtent pe|
|00004900| 72 6d 69 74 74 65 64 20 | 62 79 0a 58 20 20 61 70 |rmitted |by.X  ap|
|00004910| 70 6c 69 63 61 62 6c 65 | 20 6c 61 77 2e 20 20 54 |plicable| law.  T|
|00004920| 68 69 73 20 70 72 6f 67 | 72 61 6d 20 69 73 20 70 |his prog|ram is p|
|00004930| 72 6f 76 69 64 65 64 20 | 22 41 53 20 49 53 22 20 |rovided |"AS IS" |
|00004940| 77 69 74 68 6f 75 74 20 | 77 61 72 72 61 6e 74 79 |without |warranty|
|00004950| 20 6f 66 0a 58 20 20 61 | 6e 79 20 6b 69 6e 64 2c | of.X  a|ny kind,|
|00004960| 20 65 69 74 68 65 72 20 | 65 78 70 72 65 73 73 65 | either |expresse|
|00004970| 64 20 6f 72 20 69 6d 70 | 6c 69 65 64 2c 20 69 6e |d or imp|lied, in|
|00004980| 63 6c 75 64 69 6e 67 2c | 20 62 75 74 20 6e 6f 74 |cluding,| but not|
|00004990| 20 6c 69 6d 69 74 65 64 | 20 74 6f 2c 0a 58 20 20 | limited| to,.X  |
|000049a0| 74 68 65 20 69 6d 70 6c | 69 65 64 20 77 61 72 72 |the impl|ied warr|
|000049b0| 61 6e 74 69 65 73 20 6f | 66 20 6d 65 72 63 68 61 |anties o|f mercha|
|000049c0| 6e 74 61 62 69 6c 69 74 | 79 20 61 6e 64 20 66 69 |ntabilit|y and fi|
|000049d0| 74 6e 65 73 73 20 66 6f | 72 20 61 20 70 61 72 74 |tness fo|r a part|
|000049e0| 69 63 75 6c 61 72 20 0a | 58 20 20 70 75 72 70 6f |icular .|X  purpo|
|000049f0| 73 65 2e 20 20 54 68 65 | 20 65 6e 74 69 72 65 20 |se.  The| entire |
|00004a00| 72 69 73 6b 20 61 73 20 | 74 6f 20 74 68 65 20 71 |risk as |to the q|
|00004a10| 75 61 6c 69 74 79 20 61 | 6e 64 20 70 65 72 66 6f |uality a|nd perfo|
|00004a20| 72 6d 61 6e 63 65 20 6f | 66 20 74 68 69 73 20 0a |rmance o|f this .|
|00004a30| 58 20 20 70 72 6f 67 72 | 61 6d 20 69 73 20 77 69 |X  progr|am is wi|
|00004a40| 74 68 20 74 68 65 20 75 | 73 65 72 2e 20 20 53 68 |th the u|ser.  Sh|
|00004a50| 6f 75 6c 64 20 74 68 69 | 73 20 70 72 6f 67 72 61 |ould thi|s progra|
|00004a60| 6d 20 70 72 6f 76 65 20 | 64 65 66 65 63 74 69 76 |m prove |defectiv|
|00004a70| 65 2c 20 74 68 65 20 0a | 58 20 20 75 73 65 72 20 |e, the .|X  user |
|00004a80| 61 73 73 75 6d 65 73 20 | 74 68 65 20 63 6f 73 74 |assumes |the cost|
|00004a90| 20 6f 66 20 61 6c 6c 20 | 6e 65 63 65 73 73 61 72 | of all |necessar|
|00004aa0| 79 20 73 65 72 76 69 63 | 69 6e 67 2c 20 72 65 70 |y servic|ing, rep|
|00004ab0| 61 69 72 20 6f 72 20 63 | 6f 72 72 65 63 74 69 6f |air or c|orrectio|
|00004ac0| 6e 2e 0a 58 0a 58 20 20 | 28 33 29 20 49 6e 20 6e |n..X.X  |(3) In n|
|00004ad0| 6f 20 65 76 65 6e 74 20 | 75 6e 6c 65 73 73 20 72 |o event |unless r|
|00004ae0| 65 71 75 69 72 65 64 20 | 62 79 20 61 70 70 6c 69 |equired |by appli|
|00004af0| 63 61 62 6c 65 20 6c 61 | 77 20 77 69 6c 6c 20 74 |cable la|w will t|
|00004b00| 68 65 20 63 6f 70 79 72 | 69 67 68 74 0a 58 20 20 |he copyr|ight.X  |
|00004b10| 68 6f 6c 64 65 72 20 62 | 65 20 6c 69 61 62 6c 65 |holder b|e liable|
|00004b20| 20 74 6f 20 74 68 65 20 | 75 73 65 72 20 66 6f 72 | to the |user for|
|00004b30| 20 64 61 6d 61 67 65 73 | 2c 20 69 6e 63 6c 75 64 | damages|, includ|
|00004b40| 69 6e 67 20 61 6e 79 20 | 67 65 6e 65 72 61 6c 2c |ing any |general,|
|00004b50| 0a 58 20 20 73 70 65 63 | 69 61 6c 2c 20 69 6e 63 |.X  spec|ial, inc|
|00004b60| 69 64 65 6e 74 61 6c 20 | 6f 72 20 63 6f 6e 73 65 |idental |or conse|
|00004b70| 71 75 65 6e 74 69 61 6c | 20 64 61 6d 61 67 65 73 |quential| damages|
|00004b80| 20 61 72 69 73 69 6e 67 | 20 6f 75 74 20 6f 66 20 | arising| out of |
|00004b90| 74 68 65 20 75 73 65 0a | 58 20 20 6f 72 20 69 6e |the use.|X  or in|
|00004ba0| 61 62 69 6c 69 74 79 20 | 74 6f 20 75 73 65 20 74 |ability |to use t|
|00004bb0| 68 69 73 20 70 72 6f 67 | 72 61 6d 20 28 69 6e 63 |his prog|ram (inc|
|00004bc0| 6c 75 64 69 6e 67 20 62 | 75 74 20 6e 6f 74 20 6c |luding b|ut not l|
|00004bd0| 69 6d 69 74 65 64 20 74 | 6f 20 6c 6f 73 73 20 6f |imited t|o loss o|
|00004be0| 66 0a 58 20 20 64 61 74 | 61 20 6f 72 20 64 61 74 |f.X  dat|a or dat|
|00004bf0| 61 20 62 65 69 6e 67 20 | 72 65 6e 64 65 72 65 64 |a being |rendered|
|00004c00| 20 69 6e 61 63 63 75 72 | 61 74 65 20 6f 72 20 6c | inaccur|ate or l|
|00004c10| 6f 73 73 65 73 20 73 75 | 73 74 61 69 6e 65 64 20 |osses su|stained |
|00004c20| 62 79 20 74 68 65 0a 58 | 20 20 75 73 65 72 20 6f |by the.X|  user o|
|00004c30| 72 20 74 68 69 72 64 20 | 70 61 72 74 69 65 73 20 |r third |parties |
|00004c40| 6f 72 20 61 20 66 61 69 | 6c 75 72 65 20 6f 66 20 |or a fai|lure of |
|00004c50| 74 68 69 73 20 70 72 6f | 67 72 61 6d 20 74 6f 20 |this pro|gram to |
|00004c60| 6f 70 65 72 61 74 65 20 | 77 69 74 68 20 61 6e 79 |operate |with any|
|00004c70| 0a 58 20 20 6f 74 68 65 | 72 20 70 72 6f 67 72 61 |.X  othe|r progra|
|00004c80| 6d 73 29 2c 20 65 76 65 | 6e 20 69 66 20 73 75 63 |ms), eve|n if suc|
|00004c90| 68 20 68 6f 6c 64 65 72 | 20 6f 72 20 74 68 69 72 |h holder| or thir|
|00004ca0| 64 20 70 61 72 74 79 20 | 68 61 73 20 62 65 65 6e |d party |has been|
|00004cb0| 20 61 64 76 69 73 65 64 | 0a 58 20 20 6f 66 20 74 | advised|.X  of t|
|00004cc0| 68 65 20 70 6f 73 73 69 | 62 69 6c 69 74 79 20 6f |he possi|bility o|
|00004cd0| 66 20 73 75 63 68 20 64 | 61 6d 61 67 65 73 2e 0a |f such d|amages..|
|00004ce0| 58 0a 58 20 20 28 34 29 | 20 4f 62 6a 65 63 74 20 |X.X  (4)| Object |
|00004cf0| 63 6f 64 65 20 70 72 6f | 64 75 63 65 64 20 62 79 |code pro|duced by|
|00004d00| 20 61 20 63 6f 6d 70 69 | 6c 65 72 20 66 72 6f 6d | a compi|ler from|
|00004d10| 20 74 68 69 73 20 63 6f | 64 65 20 6d 61 79 20 62 | this co|de may b|
|00004d20| 65 20 0a 58 20 20 69 6e | 63 6f 72 70 6f 72 61 74 |e .X  in|corporat|
|00004d30| 65 64 20 69 6e 74 6f 20 | 63 6f 6d 6d 65 72 63 69 |ed into |commerci|
|00004d40| 61 6c 20 70 72 6f 64 75 | 63 74 73 20 77 69 74 68 |al produ|cts with|
|00004d50| 6f 75 74 20 62 65 69 6e | 67 20 73 75 62 6a 65 63 |out bein|g subjec|
|00004d60| 74 20 74 6f 20 0a 58 20 | 20 72 65 73 74 72 69 63 |t to .X | restric|
|00004d70| 74 69 6f 6e 73 20 28 31 | 29 28 61 29 20 6f 72 20 |tions (1|)(a) or |
|00004d80| 28 31 29 28 62 29 2e 0a | 58 0a 58 2a 2f 0a 58 0a |(1)(b)..|X.X*/.X.|
|00004d90| 58 23 69 6e 63 6c 75 64 | 65 20 3c 73 74 64 69 6f |X#includ|e <stdio|
|00004da0| 2e 68 3e 0a 58 23 69 6e | 63 6c 75 64 65 20 3c 6d |.h>.X#in|clude <m|
|00004db0| 61 6c 6c 6f 63 2e 68 3e | 0a 58 23 69 6e 63 6c 75 |alloc.h>|.X#inclu|
|00004dc0| 64 65 20 3c 6d 65 6d 6f | 72 79 2e 68 3e 0a 58 23 |de <memo|ry.h>.X#|
|00004dd0| 69 6e 63 6c 75 64 65 20 | 3c 73 74 72 69 6e 67 2e |include |<string.|
|00004de0| 68 3e 0a 58 23 69 6e 63 | 6c 75 64 65 20 3c 73 69 |h>.X#inc|lude <si|
|00004df0| 67 6e 61 6c 2e 68 3e 0a | 58 23 69 6e 63 6c 75 64 |gnal.h>.|X#includ|
|00004e00| 65 20 3c 73 65 74 6a 6d | 70 2e 68 3e 0a 58 0a 58 |e <setjm|p.h>.X.X|
|00004e10| 23 69 6e 63 6c 75 64 65 | 20 3c 73 79 73 2f 74 79 |#include| <sys/ty|
|00004e20| 70 65 73 2e 68 3e 0a 58 | 23 69 6e 63 6c 75 64 65 |pes.h>.X|#include|
|00004e30| 20 3c 73 79 73 2f 74 69 | 6d 65 73 2e 68 3e 0a 58 | <sys/ti|mes.h>.X|
|00004e40| 23 69 6e 63 6c 75 64 65 | 20 3c 73 79 73 2f 70 61 |#include| <sys/pa|
|00004e50| 72 61 6d 2e 68 3e 0a 58 | 0a 58 23 69 6e 63 6c 75 |ram.h>.X|.X#inclu|
|00004e60| 64 65 20 22 73 6f 72 74 | 69 6e 67 2e 68 22 0a 58 |de "sort|ing.h".X|
|00004e70| 0a 58 23 64 65 66 69 6e | 65 20 54 45 53 54 5f 54 |.X#defin|e TEST_T|
|00004e80| 59 50 45 20 64 6f 75 62 | 6c 65 0a 58 23 64 65 66 |YPE doub|le.X#def|
|00004e90| 69 6e 65 20 54 45 53 54 | 5f 46 55 4e 43 20 64 6f |ine TEST|_FUNC do|
|00004ea0| 75 62 6c 65 5f 63 6f 6d | 70 61 72 65 0a 58 23 64 |uble_com|pare.X#d|
|00004eb0| 65 66 69 6e 65 20 44 45 | 46 41 55 4c 54 5f 43 4f |efine DE|FAULT_CO|
|00004ec0| 55 4e 54 20 32 32 32 30 | 20 2f 2a 20 70 72 6f 64 |UNT 2220| /* prod|
|00004ed0| 75 63 74 20 6f 66 20 34 | 20 61 6e 64 20 73 65 76 |uct of 4| and sev|
|00004ee0| 65 72 61 6c 20 70 72 69 | 6d 65 73 20 2a 2f 0a 58 |eral pri|mes */.X|
|00004ef0| 0a 58 23 64 65 66 69 6e | 65 20 43 41 4e 41 52 59 |.X#defin|e CANARY|
|00004f00| 5f 4c 4f 57 20 2d 37 37 | 2e 30 0a 58 23 64 65 66 |_LOW -77|.0.X#def|
|00004f10| 69 6e 65 20 43 41 4e 41 | 52 59 5f 48 49 47 48 20 |ine CANA|RY_HIGH |
|00004f20| 2d 38 38 2e 30 0a 58 0a | 58 23 64 65 66 69 6e 65 |-88.0.X.|X#define|
|00004f30| 20 54 45 53 54 5f 52 41 | 4e 44 4f 4d 20 31 0a 58 | TEST_RA|NDOM 1.X|
|00004f40| 23 64 65 66 69 6e 65 20 | 54 45 53 54 5f 41 53 43 |#define |TEST_ASC|
|00004f50| 45 4e 44 20 32 0a 58 23 | 64 65 66 69 6e 65 20 54 |END 2.X#|define T|
|00004f60| 45 53 54 5f 44 45 53 43 | 45 4e 44 20 33 0a 58 23 |EST_DESC|END 3.X#|
|00004f70| 64 65 66 69 6e 65 20 54 | 45 53 54 5f 46 49 42 5f |define T|EST_FIB_|
|00004f80| 41 53 43 20 34 0a 58 23 | 64 65 66 69 6e 65 20 54 |ASC 4.X#|define T|
|00004f90| 45 53 54 5f 46 49 42 5f | 44 45 53 43 20 35 0a 58 |EST_FIB_|DESC 5.X|
|00004fa0| 23 64 65 66 69 6e 65 20 | 54 45 53 54 5f 53 55 52 |#define |TEST_SUR|
|00004fb0| 50 52 49 53 45 20 36 0a | 58 23 64 65 66 69 6e 65 |PRISE 6.|X#define|
|00004fc0| 20 54 45 53 54 5f 4d 4f | 53 54 4c 59 20 37 0a 58 | TEST_MO|STLY 7.X|
|00004fd0| 23 64 65 66 69 6e 65 20 | 54 45 53 54 5f 45 51 55 |#define |TEST_EQU|
|00004fe0| 49 56 20 38 0a 58 0a 58 | 73 74 61 74 69 63 20 69 |IV 8.X.X|static i|
|00004ff0| 6e 74 20 63 6f 6d 70 61 | 72 65 5f 63 6f 75 6e 74 |nt compa|re_count|
|00005000| 3b 0a 58 73 74 61 74 69 | 63 20 69 6e 74 20 73 5f |;.Xstati|c int s_|
|00005010| 68 65 61 70 3b 0a 58 73 | 74 61 74 69 63 20 63 68 |heap;.Xs|tatic ch|
|00005020| 61 72 20 2a 20 73 5f 6c | 6f 77 2c 20 2a 20 73 5f |ar * s_l|ow, * s_|
|00005030| 68 69 67 68 3b 0a 58 0a | 58 23 64 65 66 69 6e 65 |high;.X.|X#define|
|00005040| 20 43 48 45 43 4b 5f 43 | 41 4e 41 52 49 45 53 20 | CHECK_C|ANARIES |
|00005050| 5c 0a 58 20 20 7b 20 5c | 0a 58 20 20 20 20 69 66 |\.X  { \|.X    if|
|00005060| 20 28 2a 28 54 45 53 54 | 5f 54 59 50 45 20 2a 29 | (*(TEST|_TYPE *)|
|00005070| 20 61 20 3d 3d 20 43 41 | 4e 41 52 59 5f 4c 4f 57 | a == CA|NARY_LOW|
|00005080| 20 7c 7c 20 2a 28 54 45 | 53 54 5f 54 59 50 45 20 | || *(TE|ST_TYPE |
|00005090| 2a 29 20 62 20 3d 3d 20 | 43 41 4e 41 52 59 5f 4c |*) b == |CANARY_L|
|000050a0| 4f 57 29 5c 0a 58 20 20 | 20 20 7b 20 5c 0a 58 20 |OW)\.X  |  { \.X |
|000050b0| 20 20 20 20 20 70 72 69 | 6e 74 66 28 22 72 61 6e |     pri|ntf("ran|
|000050c0| 20 6f 66 66 20 74 68 65 | 20 62 6f 74 74 6f 6d 20 | off the| bottom |
|000050d0| 6f 66 20 74 68 65 20 61 | 72 72 61 79 21 5c 6e 22 |of the a|rray!\n"|
|000050e0| 29 3b 20 5c 0a 58 20 20 | 20 20 20 20 66 66 6c 75 |); \.X  |    fflu|
|000050f0| 73 68 28 73 74 64 6f 75 | 74 29 3b 20 5c 0a 58 20 |sh(stdou|t); \.X |
|00005100| 20 20 20 20 20 6c 6f 6e | 67 6a 6d 70 28 6e 65 78 |     lon|gjmp(nex|
|00005110| 74 2c 20 31 29 3b 20 5c | 0a 58 20 20 20 20 7d 20 |t, 1); \|.X    } |
|00005120| 5c 0a 58 20 20 20 20 69 | 66 20 28 2a 28 54 45 53 |\.X    i|f (*(TES|
|00005130| 54 5f 54 59 50 45 20 2a | 29 20 61 20 3d 3d 20 43 |T_TYPE *|) a == C|
|00005140| 41 4e 41 52 59 5f 48 49 | 47 48 20 7c 7c 20 2a 28 |ANARY_HI|GH || *(|
|00005150| 54 45 53 54 5f 54 59 50 | 45 20 2a 29 20 62 20 3d |TEST_TYP|E *) b =|
|00005160| 3d 20 43 41 4e 41 52 59 | 5f 48 49 47 48 29 5c 0a |= CANARY|_HIGH)\.|
|00005170| 58 20 20 20 20 7b 20 5c | 0a 58 20 20 20 20 20 20 |X    { \|.X      |
|00005180| 70 72 69 6e 74 66 28 22 | 72 61 6e 20 6f 66 66 20 |printf("|ran off |
|00005190| 74 68 65 20 74 6f 70 20 | 6f 66 20 74 68 65 20 61 |the top |of the a|
|000051a0| 72 72 61 79 21 5c 6e 22 | 29 3b 20 5c 0a 58 20 20 |rray!\n"|); \.X  |
|000051b0| 20 20 20 20 66 66 6c 75 | 73 68 28 73 74 64 6f 75 |    fflu|sh(stdou|
|000051c0| 74 29 3b 20 5c 0a 58 20 | 20 20 20 20 20 6c 6f 6e |t); \.X |     lon|
|000051d0| 67 6a 6d 70 28 6e 65 78 | 74 2c 20 31 29 3b 20 5c |gjmp(nex|t, 1); \|
|000051e0| 0a 58 20 20 20 20 7d 20 | 5c 0a 58 20 20 7d 0a 58 |.X    } |\.X  }.X|
|000051f0| 0a 58 23 64 65 66 69 6e | 65 20 55 50 44 41 54 45 |.X#defin|e UPDATE|
|00005200| 5f 53 5f 48 45 41 50 20 | 5c 0a 58 20 20 7b 20 73 |_S_HEAP |\.X  { s|
|00005210| 74 72 75 63 74 20 6d 61 | 6c 6c 69 6e 66 6f 20 6d |truct ma|llinfo m|
|00005220| 69 3b 20 5c 0a 58 20 20 | 20 20 6d 69 20 3d 20 6d |i; \.X  |  mi = m|
|00005230| 61 6c 6c 69 6e 66 6f 28 | 29 3b 20 20 5c 0a 58 20 |allinfo(|);  \.X |
|00005240| 20 20 20 69 66 20 28 73 | 5f 68 65 61 70 20 3c 20 |   if (s|_heap < |
|00005250| 6d 69 2e 75 6f 72 64 62 | 6c 6b 73 29 20 73 5f 68 |mi.uordb|lks) s_h|
|00005260| 65 61 70 20 3d 20 6d 69 | 2e 75 6f 72 64 62 6c 6b |eap = mi|.uordblk|
|00005270| 73 3b 20 20 5c 0a 58 20 | 20 20 20 69 66 20 28 73 |s;  \.X |   if (s|
|00005280| 5f 6c 6f 77 20 3d 3d 20 | 4e 55 4c 4c 20 7c 7c 20 |_low == |NULL || |
|00005290| 77 68 65 72 65 20 3c 20 | 73 5f 6c 6f 77 29 20 73 |where < |s_low) s|
|000052a0| 5f 6c 6f 77 20 3d 20 77 | 68 65 72 65 3b 20 5c 0a |_low = w|here; \.|
|000052b0| 58 20 20 20 20 69 66 20 | 28 73 5f 68 69 67 68 20 |X    if |(s_high |
|000052c0| 3d 3d 20 4e 55 4c 4c 20 | 7c 7c 20 77 68 65 72 65 |== NULL ||| where|
|000052d0| 20 3e 20 73 5f 68 69 67 | 68 29 20 73 5f 68 69 67 | > s_hig|h) s_hig|
|000052e0| 68 20 3d 20 77 68 65 72 | 65 3b 20 5c 0a 58 20 20 |h = wher|e; \.X  |
|000052f0| 20 20 63 6f 6d 70 61 72 | 65 5f 63 6f 75 6e 74 20 |  compar|e_count |
|00005300| 2b 2b 3b 20 7d 0a 58 0a | 58 73 74 61 74 69 63 20 |++; }.X.|Xstatic |
|00005310| 6a 6d 70 5f 62 75 66 20 | 6e 65 78 74 3b 0a 58 0a |jmp_buf |next;.X.|
|00005320| 58 76 6f 69 64 20 63 61 | 74 63 68 5f 71 75 69 74 |Xvoid ca|tch_quit|
|00005330| 28 29 0a 58 7b 0a 58 20 | 20 70 72 69 6e 74 66 28 |().X{.X | printf(|
|00005340| 22 5c 6e 22 29 3b 0a 58 | 20 20 66 66 6c 75 73 68 |"\n");.X|  fflush|
|00005350| 28 73 74 64 6f 75 74 29 | 3b 0a 58 20 20 6c 6f 6e |(stdout)|;.X  lon|
|00005360| 67 6a 6d 70 28 6e 65 78 | 74 2c 20 31 29 3b 0a 58 |gjmp(nex|t, 1);.X|
|00005370| 7d 0a 58 0a 58 76 6f 69 | 64 20 74 65 73 74 5f 73 |}.X.Xvoi|d test_s|
|00005380| 6f 72 74 5f 66 75 6e 63 | 28 29 3b 0a 58 0a 58 69 |ort_func|();.X.Xi|
|00005390| 6e 74 20 69 6e 74 5f 63 | 6f 6d 70 61 72 65 28 61 |nt int_c|ompare(a|
|000053a0| 2c 20 62 29 20 69 6e 74 | 20 2a 20 61 2c 20 2a 62 |, b) int| * a, *b|
|000053b0| 3b 20 0a 58 7b 20 0a 58 | 20 20 63 68 61 72 20 66 |; .X{ .X|  char f|
|000053c0| 6f 6f 3b 0a 58 20 20 63 | 68 61 72 20 2a 20 77 68 |oo;.X  c|har * wh|
|000053d0| 65 72 65 20 3d 20 26 66 | 6f 6f 3b 0a 58 0a 58 20 |ere = &f|oo;.X.X |
|000053e0| 20 43 48 45 43 4b 5f 43 | 41 4e 41 52 49 45 53 3b | CHECK_C|ANARIES;|
|000053f0| 0a 58 20 20 55 50 44 41 | 54 45 5f 53 5f 48 45 41 |.X  UPDA|TE_S_HEA|
|00005400| 50 3b 0a 58 0a 58 20 20 | 69 66 20 28 2a 61 20 3e |P;.X.X  |if (*a >|
|00005410| 20 2a 62 29 20 72 65 74 | 75 72 6e 20 31 3b 0a 58 | *b) ret|urn 1;.X|
|00005420| 20 20 69 66 20 28 2a 61 | 20 3c 20 2a 62 29 20 72 |  if (*a| < *b) r|
|00005430| 65 74 75 72 6e 20 2d 31 | 3b 0a 58 20 20 72 65 74 |eturn -1|;.X  ret|
|00005440| 75 72 6e 20 30 3b 0a 58 | 7d 0a 58 0a 58 69 6e 74 |urn 0;.X|}.X.Xint|
|00005450| 20 64 6f 75 62 6c 65 5f | 63 6f 6d 70 61 72 65 28 | double_|compare(|
|00005460| 61 2c 20 62 29 20 64 6f | 75 62 6c 65 20 2a 20 61 |a, b) do|uble * a|
|00005470| 2c 20 2a 62 3b 20 0a 58 | 7b 20 0a 58 20 20 63 68 |, *b; .X|{ .X  ch|
|00005480| 61 72 20 66 6f 6f 3b 0a | 58 20 20 63 68 61 72 20 |ar foo;.|X  char |
|00005490| 2a 20 77 68 65 72 65 20 | 3d 20 26 66 6f 6f 3b 0a |* where |= &foo;.|
|000054a0| 58 0a 58 20 20 43 48 45 | 43 4b 5f 43 41 4e 41 52 |X.X  CHE|CK_CANAR|
|000054b0| 49 45 53 3b 0a 58 20 20 | 55 50 44 41 54 45 5f 53 |IES;.X  |UPDATE_S|
|000054c0| 5f 48 45 41 50 3b 0a 58 | 0a 58 20 20 69 66 20 28 |_HEAP;.X|.X  if (|
|000054d0| 2a 61 20 3e 20 2a 62 29 | 20 72 65 74 75 72 6e 20 |*a > *b)| return |
|000054e0| 31 3b 0a 58 20 20 69 66 | 20 28 2a 61 20 3c 20 2a |1;.X  if| (*a < *|
|000054f0| 62 29 20 72 65 74 75 72 | 6e 20 2d 31 3b 0a 58 20 |b) retur|n -1;.X |
|00005500| 20 72 65 74 75 72 6e 20 | 30 3b 0a 58 7d 0a 58 0a | return |0;.X}.X.|
|00005510| 58 2f 2a 41 52 47 53 55 | 53 45 44 2a 2f 0a 58 69 |X/*ARGSU|SED*/.Xi|
|00005520| 6e 74 20 6c 69 65 5f 61 | 73 63 65 6e 64 69 6e 67 |nt lie_a|scending|
|00005530| 28 61 2c 20 62 29 20 63 | 68 61 72 20 2a 20 61 2c |(a, b) c|har * a,|
|00005540| 20 2a 62 3b 20 0a 58 7b | 20 0a 58 20 20 63 68 61 | *b; .X{| .X  cha|
|00005550| 72 20 66 6f 6f 3b 0a 58 | 20 20 63 68 61 72 20 2a |r foo;.X|  char *|
|00005560| 20 77 68 65 72 65 20 3d | 20 26 66 6f 6f 3b 0a 58 | where =| &foo;.X|
|00005570| 0a 58 20 20 43 48 45 43 | 4b 5f 43 41 4e 41 52 49 |.X  CHEC|K_CANARI|
|00005580| 45 53 3b 0a 58 20 20 55 | 50 44 41 54 45 5f 53 5f |ES;.X  U|PDATE_S_|
|00005590| 48 45 41 50 3b 0a 58 0a | 58 20 20 72 65 74 75 72 |HEAP;.X.|X  retur|
|000055a0| 6e 20 2d 31 3b 0a 58 7d | 0a 58 0a 58 2f 2a 41 52 |n -1;.X}|.X.X/*AR|
|000055b0| 47 53 55 53 45 44 2a 2f | 0a 58 69 6e 74 20 6c 69 |GSUSED*/|.Xint li|
|000055c0| 65 5f 64 65 73 63 65 6e | 64 69 6e 67 28 61 2c 20 |e_descen|ding(a, |
|000055d0| 62 29 20 63 68 61 72 20 | 2a 20 61 2c 20 2a 62 3b |b) char |* a, *b;|
|000055e0| 20 0a 58 7b 20 0a 58 20 | 20 63 68 61 72 20 66 6f | .X{ .X | char fo|
|000055f0| 6f 3b 0a 58 20 20 63 68 | 61 72 20 2a 20 77 68 65 |o;.X  ch|ar * whe|
|00005600| 72 65 20 3d 20 26 66 6f | 6f 3b 0a 58 0a 58 20 20 |re = &fo|o;.X.X  |
|00005610| 43 48 45 43 4b 5f 43 41 | 4e 41 52 49 45 53 3b 0a |CHECK_CA|NARIES;.|
|00005620| 58 20 20 55 50 44 41 54 | 45 5f 53 5f 48 45 41 50 |X  UPDAT|E_S_HEAP|
|00005630| 3b 0a 58 0a 58 20 20 72 | 65 74 75 72 6e 20 31 3b |;.X.X  r|eturn 1;|
|00005640| 0a 58 7d 0a 58 0a 58 2f | 2a 41 52 47 53 55 53 45 |.X}.X.X/|*ARGSUSE|
|00005650| 44 2a 2f 0a 58 69 6e 74 | 20 6c 69 65 5f 65 71 75 |D*/.Xint| lie_equ|
|00005660| 61 6c 28 61 2c 20 62 29 | 20 63 68 61 72 20 2a 20 |al(a, b)| char * |
|00005670| 61 2c 20 2a 62 3b 20 0a | 58 7b 20 0a 58 20 20 63 |a, *b; .|X{ .X  c|
|00005680| 68 61 72 20 66 6f 6f 3b | 0a 58 20 20 63 68 61 72 |har foo;|.X  char|
|00005690| 20 2a 20 77 68 65 72 65 | 20 3d 20 26 66 6f 6f 3b | * where| = &foo;|
|000056a0| 0a 58 0a 58 20 20 43 48 | 45 43 4b 5f 43 41 4e 41 |.X.X  CH|ECK_CANA|
|000056b0| 52 49 45 53 3b 0a 58 20 | 20 55 50 44 41 54 45 5f |RIES;.X | UPDATE_|
|000056c0| 53 5f 48 45 41 50 3b 0a | 58 0a 58 20 20 72 65 74 |S_HEAP;.|X.X  ret|
|000056d0| 75 72 6e 20 30 3b 0a 58 | 7d 0a 58 0a 58 2f 2a 41 |urn 0;.X|}.X.X/*A|
|000056e0| 52 47 53 55 53 45 44 2a | 2f 0a 58 69 6e 74 20 73 |RGSUSED*|/.Xint s|
|000056f0| 75 72 70 72 69 73 65 28 | 61 2c 20 62 29 20 63 68 |urprise(|a, b) ch|
|00005700| 61 72 20 2a 20 61 2c 20 | 2a 62 3b 20 0a 58 7b 20 |ar * a, |*b; .X{ |
|00005710| 0a 58 20 20 63 68 61 72 | 20 66 6f 6f 3b 0a 58 20 |.X  char| foo;.X |
|00005720| 20 63 68 61 72 20 2a 20 | 77 68 65 72 65 20 3d 20 | char * |where = |
|00005730| 26 66 6f 6f 3b 0a 58 0a | 58 20 20 43 48 45 43 4b |&foo;.X.|X  CHECK|
|00005740| 5f 43 41 4e 41 52 49 45 | 53 3b 0a 58 20 20 55 50 |_CANARIE|S;.X  UP|
|00005750| 44 41 54 45 5f 53 5f 48 | 45 41 50 3b 0a 58 0a 58 |DATE_S_H|EAP;.X.X|
|00005760| 20 20 66 6f 6f 20 3d 20 | 72 61 6e 64 28 29 20 3e |  foo = |rand() >|
|00005770| 3e 20 32 33 3b 0a 58 20 | 20 69 66 20 28 28 75 6e |> 23;.X | if ((un|
|00005780| 73 69 67 6e 65 64 20 63 | 68 61 72 29 20 66 6f 6f |signed c|har) foo|
|00005790| 20 3c 20 38 35 29 20 72 | 65 74 75 72 6e 20 2d 31 | < 85) r|eturn -1|
|000057a0| 3b 0a 58 20 20 69 66 20 | 28 28 75 6e 73 69 67 6e |;.X  if |((unsign|
|000057b0| 65 64 20 63 68 61 72 29 | 20 66 6f 6f 20 3c 20 31 |ed char)| foo < 1|
|000057c0| 37 31 29 20 72 65 74 75 | 72 6e 20 30 3b 0a 58 20 |71) retu|rn 0;.X |
|000057d0| 20 72 65 74 75 72 6e 20 | 31 3b 0a 58 7d 0a 58 0a | return |1;.X}.X.|
|000057e0| 58 69 6e 74 20 6d 61 69 | 6e 28 61 72 67 63 2c 20 |Xint mai|n(argc, |
|000057f0| 61 72 67 76 29 20 69 6e | 74 20 61 72 67 63 3b 20 |argv) in|t argc; |
|00005800| 63 68 61 72 20 2a 20 61 | 72 67 76 5b 5d 3b 0a 58 |char * a|rgv[];.X|
|00005810| 7b 0a 58 20 20 69 6e 74 | 20 6e 3b 0a 58 20 20 69 |{.X  int| n;.X  i|
|00005820| 6e 74 20 73 74 61 67 65 | 20 3d 20 30 3b 0a 58 20 |nt stage| = 0;.X |
|00005830| 20 69 6e 74 20 64 6f 6e | 65 20 3d 20 30 3b 0a 58 | int don|e = 0;.X|
|00005840| 0a 58 20 20 70 72 69 6e | 74 66 28 22 73 6f 72 74 |.X  prin|tf("sort|
|00005850| 20 66 6c 6f 67 67 65 72 | 20 76 65 72 73 69 6f 6e | flogger| version|
|00005860| 20 25 64 20 70 61 74 63 | 68 20 6c 65 76 65 6c 20 | %d patc|h level |
|00005870| 25 64 2e 5c 6e 22 2c 0a | 58 20 20 20 20 46 4c 4f |%d.\n",.|X    FLO|
|00005880| 47 47 45 52 5f 56 45 52 | 53 49 4f 4e 2c 20 46 4c |GGER_VER|SION, FL|
|00005890| 4f 47 47 45 52 5f 50 41 | 54 43 48 4c 45 56 45 4c |OGGER_PA|TCHLEVEL|
|000058a0| 29 3b 0a 58 20 20 69 66 | 20 28 61 72 67 63 20 3e |);.X  if| (argc >|
|000058b0| 20 31 29 20 0a 58 20 20 | 20 20 6e 20 3d 20 61 74 | 1) .X  |  n = at|
|000058c0| 6f 69 28 61 72 67 76 5b | 31 5d 29 3b 0a 58 20 20 |oi(argv[|1]);.X  |
|000058d0| 65 6c 73 65 0a 58 20 20 | 20 20 6e 20 3d 20 44 45 |else.X  |  n = DE|
|000058e0| 46 41 55 4c 54 5f 43 4f | 55 4e 54 3b 0a 58 20 20 |FAULT_CO|UNT;.X  |
|000058f0| 69 66 20 28 6e 20 3c 20 | 30 29 20 6e 20 3d 20 2d |if (n < |0) n = -|
|00005900| 6e 3b 0a 58 0a 58 20 20 | 70 72 69 6e 74 66 28 22 |n;.X.X  |printf("|
|00005910| 74 69 6d 65 72 20 72 65 | 73 6f 6c 75 74 69 6f 6e |timer re|solution|
|00005920| 20 3d 20 25 31 2e 36 66 | 5c 6e 22 2c 20 31 2e 30 | = %1.6f|\n", 1.0|
|00005930| 2f 28 64 6f 75 62 6c 65 | 29 48 5a 29 3b 0a 58 20 |/(double|)HZ);.X |
|00005940| 20 70 72 69 6e 74 66 28 | 22 65 6c 65 6d 65 6e 74 | printf(|"element|
|00005950| 20 73 69 7a 65 20 3d 20 | 25 64 5c 6e 22 2c 20 73 | size = |%d\n", s|
|00005960| 69 7a 65 6f 66 28 54 45 | 53 54 5f 54 59 50 45 29 |izeof(TE|ST_TYPE)|
|00005970| 29 3b 0a 58 20 20 70 72 | 69 6e 74 66 28 22 6e 75 |);.X  pr|intf("nu|
|00005980| 6d 62 65 72 20 6f 66 20 | 65 6c 65 6d 65 6e 74 73 |mber of |elements|
|00005990| 20 3d 20 25 64 22 2c 20 | 6e 29 3b 0a 58 20 20 66 | = %d", |n);.X  f|
|000059a0| 66 6c 75 73 68 28 73 74 | 64 6f 75 74 29 3b 0a 58 |flush(st|dout);.X|
|000059b0| 0a 58 20 20 73 65 74 6a | 6d 70 28 6e 65 78 74 29 |.X  setj|mp(next)|
|000059c0| 3b 0a 58 20 20 73 69 67 | 6e 61 6c 28 53 49 47 49 |;.X  sig|nal(SIGI|
|000059d0| 4e 54 2c 20 63 61 74 63 | 68 5f 71 75 69 74 29 3b |NT, catc|h_quit);|
|000059e0| 0a 58 0a 58 20 20 2f 2a | 20 61 70 6f 6c 6f 67 69 |.X.X  /*| apologi|
|000059f0| 65 73 20 66 6f 72 20 74 | 68 65 20 62 69 7a 61 72 |es for t|he bizar|
|00005a00| 72 65 20 63 6f 64 65 20 | 6c 61 79 6f 75 74 20 2a |re code |layout *|
|00005a10| 2f 0a 58 0a 58 20 20 77 | 68 69 6c 65 20 28 21 20 |/.X.X  w|hile (! |
|00005a20| 64 6f 6e 65 29 20 73 77 | 69 74 63 68 20 28 73 74 |done) sw|itch (st|
|00005a30| 61 67 65 29 0a 58 20 20 | 7b 0a 58 20 20 20 20 63 |age).X  |{.X    c|
|00005a40| 61 73 65 20 30 3a 20 70 | 72 69 6e 74 66 28 22 5c |ase 0: p|rintf("\|
|00005a50| 6e 2a 2a 2a 20 71 73 6f | 72 74 20 2a 2a 2a 5c 6e |n*** qso|rt ***\n|
|00005a60| 22 29 3b 0a 58 20 20 20 | 20 20 20 20 20 20 20 20 |");.X   |        |
|00005a70| 20 70 72 69 6e 74 66 28 | 22 64 61 74 61 20 20 20 | printf(|"data   |
|00005a80| 20 20 20 20 20 20 63 6f | 6d 70 61 72 65 73 20 20 |      co|mpares  |
|00005a90| 20 20 20 20 73 74 61 63 | 6b 20 20 20 20 20 20 20 |    stac|k       |
|00005aa0| 22 29 3b 0a 58 20 20 20 | 20 20 20 20 20 20 20 20 |");.X   |        |
|00005ab0| 20 70 72 69 6e 74 66 28 | 22 68 65 61 70 20 20 20 | printf(|"heap   |
|00005ac0| 20 20 20 20 75 73 65 72 | 20 20 20 20 20 20 20 73 |    user|       s|
|00005ad0| 79 73 74 65 6d 5c 6e 22 | 29 3b 0a 58 20 20 20 20 |ystem\n"|);.X    |
|00005ae0| 20 20 20 20 20 20 20 20 | 66 66 6c 75 73 68 28 73 |        |fflush(s|
|00005af0| 74 64 6f 75 74 29 3b 0a | 58 20 20 20 20 20 20 20 |tdout);.|X       |
|00005b00| 20 20 20 20 20 73 74 61 | 67 65 20 2b 2b 3b 20 74 |     sta|ge ++; t|
|00005b10| 65 73 74 5f 73 6f 72 74 | 5f 66 75 6e 63 28 71 73 |est_sort|_func(qs|
|00005b20| 6f 72 74 2c 20 6e 2c 20 | 31 29 3b 20 62 72 65 61 |ort, n, |1); brea|
|00005b30| 6b 3b 0a 58 20 20 20 20 | 63 61 73 65 20 31 3a 20 |k;.X    |case 1: |
|00005b40| 73 74 61 67 65 20 2b 2b | 3b 20 74 65 73 74 5f 73 |stage ++|; test_s|
|00005b50| 6f 72 74 5f 66 75 6e 63 | 28 71 73 6f 72 74 2c 20 |ort_func|(qsort, |
|00005b60| 6e 2c 20 32 29 3b 20 62 | 72 65 61 6b 3b 0a 58 20 |n, 2); b|reak;.X |
|00005b70| 20 20 20 63 61 73 65 20 | 32 3a 20 73 74 61 67 65 |   case |2: stage|
|00005b80| 20 2b 2b 3b 20 74 65 73 | 74 5f 73 6f 72 74 5f 66 | ++; tes|t_sort_f|
|00005b90| 75 6e 63 28 71 73 6f 72 | 74 2c 20 6e 2c 20 33 29 |unc(qsor|t, n, 3)|
|00005ba0| 3b 20 62 72 65 61 6b 3b | 0a 58 20 20 20 20 63 61 |; break;|.X    ca|
|00005bb0| 73 65 20 33 3a 20 73 74 | 61 67 65 20 2b 2b 3b 20 |se 3: st|age ++; |
|00005bc0| 74 65 73 74 5f 73 6f 72 | 74 5f 66 75 6e 63 28 71 |test_sor|t_func(q|
|00005bd0| 73 6f 72 74 2c 20 6e 2c | 20 34 29 3b 20 62 72 65 |sort, n,| 4); bre|
|00005be0| 61 6b 3b 0a 58 20 20 20 | 20 63 61 73 65 20 34 3a |ak;.X   | case 4:|
|00005bf0| 20 73 74 61 67 65 20 2b | 2b 3b 20 74 65 73 74 5f | stage +|+; test_|
|00005c00| 73 6f 72 74 5f 66 75 6e | 63 28 71 73 6f 72 74 2c |sort_fun|c(qsort,|
|00005c10| 20 6e 2c 20 35 29 3b 20 | 62 72 65 61 6b 3b 0a 58 | n, 5); |break;.X|
|00005c20| 20 20 20 20 63 61 73 65 | 20 35 3a 20 73 74 61 67 |    case| 5: stag|
|00005c30| 65 20 2b 2b 3b 20 74 65 | 73 74 5f 73 6f 72 74 5f |e ++; te|st_sort_|
|00005c40| 66 75 6e 63 28 71 73 6f | 72 74 2c 20 6e 2c 20 36 |func(qso|rt, n, 6|
|00005c50| 29 3b 20 62 72 65 61 6b | 3b 0a 58 20 20 20 20 63 |); break|;.X    c|
|00005c60| 61 73 65 20 36 3a 20 73 | 74 61 67 65 20 2b 2b 3b |ase 6: s|tage ++;|
|00005c70| 20 74 65 73 74 5f 73 6f | 72 74 5f 66 75 6e 63 28 | test_so|rt_func(|
|00005c80| 71 73 6f 72 74 2c 20 6e | 2c 20 37 29 3b 20 62 72 |qsort, n|, 7); br|
|00005c90| 65 61 6b 3b 0a 58 20 20 | 20 20 63 61 73 65 20 37 |eak;.X  |  case 7|
|00005ca0| 3a 20 73 74 61 67 65 20 | 2b 2b 3b 20 74 65 73 74 |: stage |++; test|
|00005cb0| 5f 73 6f 72 74 5f 66 75 | 6e 63 28 71 73 6f 72 74 |_sort_fu|nc(qsort|
|00005cc0| 2c 20 6e 2c 20 38 29 3b | 20 62 72 65 61 6b 3b 0a |, n, 8);| break;.|
|00005cd0| 58 0a 58 20 20 20 20 63 | 61 73 65 20 31 30 3a 20 |X.X    c|ase 10: |
|00005ce0| 5f 6d 61 79 62 65 5f 73 | 6f 72 74 65 64 20 3d 20 |_maybe_s|orted = |
|00005cf0| 30 3b 0a 58 20 20 20 20 | 20 20 20 20 20 20 20 20 |0;.X    |        |
|00005d00| 20 70 72 69 6e 74 66 28 | 22 5c 6e 2a 2a 2a 20 6d | printf(|"\n*** m|
|00005d10| 65 72 67 65 5f 73 6f 72 | 74 20 2a 2a 2a 5c 6e 22 |erge_sor|t ***\n"|
|00005d20| 29 3b 0a 58 20 20 20 20 | 20 20 20 20 20 20 20 20 |);.X    |        |
|00005d30| 20 70 72 69 6e 74 66 28 | 22 64 61 74 61 20 20 20 | printf(|"data   |
|00005d40| 20 20 20 20 20 20 63 6f | 6d 70 61 72 65 73 20 20 |      co|mpares  |
|00005d50| 20 20 20 20 73 74 61 63 | 6b 20 20 20 20 20 20 20 |    stac|k       |
|00005d60| 22 29 3b 0a 58 20 20 20 | 20 20 20 20 20 20 20 20 |");.X   |        |
|00005d70| 20 20 70 72 69 6e 74 66 | 28 22 68 65 61 70 20 20 |  printf|("heap  |
|00005d80| 20 20 20 20 20 75 73 65 | 72 20 20 20 20 20 20 20 |     use|r       |
|00005d90| 73 79 73 74 65 6d 5c 6e | 22 29 3b 0a 58 20 20 20 |system\n|");.X   |
|00005da0| 20 20 20 20 20 20 20 20 | 20 20 66 66 6c 75 73 68 |        |  fflush|
|00005db0| 28 73 74 64 6f 75 74 29 | 3b 0a 58 20 20 20 20 20 |(stdout)|;.X     |
|00005dc0| 20 20 20 20 20 20 20 20 | 73 74 61 67 65 20 2b 2b |        |stage ++|
|00005dd0| 3b 20 74 65 73 74 5f 73 | 6f 72 74 5f 66 75 6e 63 |; test_s|ort_func|
|00005de0| 28 6d 65 72 67 65 5f 73 | 6f 72 74 2c 20 6e 2c 20 |(merge_s|ort, n, |
|00005df0| 31 29 3b 20 62 72 65 61 | 6b 3b 0a 58 20 20 20 20 |1); brea|k;.X    |
|00005e00| 63 61 73 65 20 31 31 3a | 20 73 74 61 67 65 20 2b |case 11:| stage +|
|00005e10| 2b 3b 20 74 65 73 74 5f | 73 6f 72 74 5f 66 75 6e |+; test_|sort_fun|
|00005e20| 63 28 6d 65 72 67 65 5f | 73 6f 72 74 2c 20 6e 2c |c(merge_|sort, n,|
|00005e30| 20 32 29 3b 20 62 72 65 | 61 6b 3b 0a 58 20 20 20 | 2); bre|ak;.X   |
|00005e40| 20 63 61 73 65 20 31 32 | 3a 20 73 74 61 67 65 20 | case 12|: stage |
|00005e50| 2b 2b 3b 20 74 65 73 74 | 5f 73 6f 72 74 5f 66 75 |++; test|_sort_fu|
|00005e60| 6e 63 28 6d 65 72 67 65 | 5f 73 6f 72 74 2c 20 6e |nc(merge|_sort, n|
|00005e70| 2c 20 33 29 3b 20 62 72 | 65 61 6b 3b 0a 58 20 20 |, 3); br|eak;.X  |
|00005e80| 20 20 63 61 73 65 20 31 | 33 3a 20 73 74 61 67 65 |  case 1|3: stage|
|00005e90| 20 2b 2b 3b 20 74 65 73 | 74 5f 73 6f 72 74 5f 66 | ++; tes|t_sort_f|
|00005ea0| 75 6e 63 28 6d 65 72 67 | 65 5f 73 6f 72 74 2c 20 |unc(merg|e_sort, |
|00005eb0| 6e 2c 20 34 29 3b 20 62 | 72 65 61 6b 3b 0a 58 20 |n, 4); b|reak;.X |
|00005ec0| 20 20 20 63 61 73 65 20 | 31 34 3a 20 73 74 61 67 |   case |14: stag|
|00005ed0| 65 20 2b 2b 3b 20 74 65 | 73 74 5f 73 6f 72 74 5f |e ++; te|st_sort_|
|00005ee0| 66 75 6e 63 28 6d 65 72 | 67 65 5f 73 6f 72 74 2c |func(mer|ge_sort,|
|00005ef0| 20 6e 2c 20 35 29 3b 20 | 62 72 65 61 6b 3b 0a 58 | n, 5); |break;.X|
|00005f00| 20 20 20 20 63 61 73 65 | 20 31 35 3a 20 73 74 61 |    case| 15: sta|
|00005f10| 67 65 20 2b 2b 3b 20 74 | 65 73 74 5f 73 6f 72 74 |ge ++; t|est_sort|
|00005f20| 5f 66 75 6e 63 28 6d 65 | 72 67 65 5f 73 6f 72 74 |_func(me|rge_sort|
|00005f30| 2c 20 6e 2c 20 36 29 3b | 20 62 72 65 61 6b 3b 0a |, n, 6);| break;.|
|00005f40| 58 20 20 20 20 63 61 73 | 65 20 31 36 3a 20 73 74 |X    cas|e 16: st|
|00005f50| 61 67 65 20 2b 2b 3b 20 | 74 65 73 74 5f 73 6f 72 |age ++; |test_sor|
|00005f60| 74 5f 66 75 6e 63 28 6d | 65 72 67 65 5f 73 6f 72 |t_func(m|erge_sor|
|00005f70| 74 2c 20 6e 2c 20 37 29 | 3b 20 62 72 65 61 6b 3b |t, n, 7)|; break;|
|00005f80| 0a 58 20 20 20 20 63 61 | 73 65 20 31 37 3a 20 73 |.X    ca|se 17: s|
|00005f90| 74 61 67 65 20 2b 2b 3b | 20 74 65 73 74 5f 73 6f |tage ++;| test_so|
|00005fa0| 72 74 5f 66 75 6e 63 28 | 6d 65 72 67 65 5f 73 6f |rt_func(|merge_so|
|00005fb0| 72 74 2c 20 6e 2c 20 38 | 29 3b 20 62 72 65 61 6b |rt, n, 8|); break|
|00005fc0| 3b 0a 58 0a 58 20 20 20 | 20 63 61 73 65 20 32 30 |;.X.X   | case 20|
|00005fd0| 3a 20 5f 6d 61 79 62 65 | 5f 73 6f 72 74 65 64 20 |: _maybe|_sorted |
|00005fe0| 3d 20 31 3b 0a 58 20 20 | 20 20 20 20 20 20 20 20 |= 1;.X  |        |
|00005ff0| 20 20 20 70 72 69 6e 74 | 66 28 22 5c 6e 2a 2a 2a |   print|f("\n***|
|00006000| 20 6d 65 72 67 65 5f 73 | 6f 72 74 28 5f 6d 61 79 | merge_s|ort(_may|
|00006010| 62 65 5f 73 6f 72 74 65 | 64 29 20 2a 2a 2a 5c 6e |be_sorte|d) ***\n|
|00006020| 22 29 3b 0a 58 20 20 20 | 20 20 20 20 20 20 20 20 |");.X   |        |
|00006030| 20 20 70 72 69 6e 74 66 | 28 22 64 61 74 61 20 20 |  printf|("data  |
|00006040| 20 20 20 20 20 20 20 63 | 6f 6d 70 61 72 65 73 20 |       c|ompares |
|00006050| 20 20 20 20 20 73 74 61 | 63 6b 20 20 20 20 20 20 |     sta|ck      |
|00006060| 20 22 29 3b 0a 58 20 20 | 20 20 20 20 20 20 20 20 | ");.X  |        |
|00006070| 20 20 20 70 72 69 6e 74 | 66 28 22 68 65 61 70 20 |   print|f("heap |
|00006080| 20 20 20 20 20 20 75 73 | 65 72 20 20 20 20 20 20 |      us|er      |
|00006090| 20 73 79 73 74 65 6d 5c | 6e 22 29 3b 0a 58 20 20 | system\|n");.X  |
|000060a0| 20 20 20 20 20 20 20 20 | 20 20 20 66 66 6c 75 73 |        |   fflus|
|000060b0| 68 28 73 74 64 6f 75 74 | 29 3b 0a 58 20 20 20 20 |h(stdout|);.X    |
|000060c0| 20 20 20 20 20 20 20 20 | 20 73 74 61 67 65 20 2b |        | stage +|
|000060d0| 2b 3b 20 74 65 73 74 5f | 73 6f 72 74 5f 66 75 6e |+; test_|sort_fun|
|000060e0| 63 28 6d 65 72 67 65 5f | 73 6f 72 74 2c 20 6e 2c |c(merge_|sort, n,|
|000060f0| 20 31 29 3b 20 62 72 65 | 61 6b 3b 0a 58 20 20 20 | 1); bre|ak;.X   |
|00006100| 20 63 61 73 65 20 32 31 | 3a 20 73 74 61 67 65 20 | case 21|: stage |
|00006110| 2b 2b 3b 20 74 65 73 74 | 5f 73 6f 72 74 5f 66 75 |++; test|_sort_fu|
|00006120| 6e 63 28 6d 65 72 67 65 | 5f 73 6f 72 74 2c 20 6e |nc(merge|_sort, n|
|00006130| 2c 20 32 29 3b 20 62 72 | 65 61 6b 3b 0a 58 20 20 |, 2); br|eak;.X  |
|00006140| 20 20 63 61 73 65 20 32 | 32 3a 20 73 74 61 67 65 |  case 2|2: stage|
|00006150| 20 2b 2b 3b 20 74 65 73 | 74 5f 73 6f 72 74 5f 66 | ++; tes|t_sort_f|
|00006160| 75 6e 63 28 6d 65 72 67 | 65 5f 73 6f 72 74 2c 20 |unc(merg|e_sort, |
|00006170| 6e 2c 20 33 29 3b 20 62 | 72 65 61 6b 3b 0a 58 20 |n, 3); b|reak;.X |
|00006180| 20 20 20 63 61 73 65 20 | 32 33 3a 20 73 74 61 67 |   case |23: stag|
|00006190| 65 20 2b 2b 3b 20 74 65 | 73 74 5f 73 6f 72 74 5f |e ++; te|st_sort_|
|000061a0| 66 75 6e 63 28 6d 65 72 | 67 65 5f 73 6f 72 74 2c |func(mer|ge_sort,|
|000061b0| 20 6e 2c 20 34 29 3b 20 | 62 72 65 61 6b 3b 0a 58 | n, 4); |break;.X|
|000061c0| 20 20 20 20 63 61 73 65 | 20 32 34 3a 20 73 74 61 |    case| 24: sta|
|000061d0| 67 65 20 2b 2b 3b 20 74 | 65 73 74 5f 73 6f 72 74 |ge ++; t|est_sort|
|000061e0| 5f 66 75 6e 63 28 6d 65 | 72 67 65 5f 73 6f 72 74 |_func(me|rge_sort|
|000061f0| 2c 20 6e 2c 20 35 29 3b | 20 62 72 65 61 6b 3b 0a |, n, 5);| break;.|
|00006200| 58 20 20 20 20 63 61 73 | 65 20 32 35 3a 20 73 74 |X    cas|e 25: st|
|00006210| 61 67 65 20 2b 2b 3b 20 | 74 65 73 74 5f 73 6f 72 |age ++; |test_sor|
|00006220| 74 5f 66 75 6e 63 28 6d | 65 72 67 65 5f 73 6f 72 |t_func(m|erge_sor|
|00006230| 74 2c 20 6e 2c 20 36 29 | 3b 20 62 72 65 61 6b 3b |t, n, 6)|; break;|
|00006240| 0a 58 20 20 20 20 63 61 | 73 65 20 32 36 3a 20 73 |.X    ca|se 26: s|
|00006250| 74 61 67 65 20 2b 2b 3b | 20 74 65 73 74 5f 73 6f |tage ++;| test_so|
|00006260| 72 74 5f 66 75 6e 63 28 | 6d 65 72 67 65 5f 73 6f |rt_func(|merge_so|
|00006270| 72 74 2c 20 6e 2c 20 37 | 29 3b 20 62 72 65 61 6b |rt, n, 7|); break|
|00006280| 3b 0a 58 20 20 20 20 63 | 61 73 65 20 32 37 3a 20 |;.X    c|ase 27: |
|00006290| 73 74 61 67 65 20 2b 2b | 3b 20 74 65 73 74 5f 73 |stage ++|; test_s|
|000062a0| 6f 72 74 5f 66 75 6e 63 | 28 6d 65 72 67 65 5f 73 |ort_func|(merge_s|
|000062b0| 6f 72 74 2c 20 6e 2c 20 | 38 29 3b 20 62 72 65 61 |ort, n, |8); brea|
|000062c0| 6b 3b 0a 58 0a 58 20 20 | 20 20 63 61 73 65 20 33 |k;.X.X  |  case 3|
|000062d0| 30 3a 20 70 72 69 6e 74 | 66 28 22 5c 6e 2a 2a 2a |0: print|f("\n***|
|000062e0| 20 68 65 61 70 5f 73 6f | 72 74 20 2a 2a 2a 5c 6e | heap_so|rt ***\n|
|000062f0| 22 29 3b 0a 58 20 20 20 | 20 20 20 20 20 20 20 20 |");.X   |        |
|00006300| 20 20 70 72 69 6e 74 66 | 28 22 64 61 74 61 20 20 |  printf|("data  |
|00006310| 20 20 20 20 20 20 20 63 | 6f 6d 70 61 72 65 73 20 |       c|ompares |
|00006320| 20 20 20 20 20 73 74 61 | 63 6b 20 20 20 20 20 20 |     sta|ck      |
|00006330| 20 22 29 3b 0a 58 20 20 | 20 20 20 20 20 20 20 20 | ");.X  |        |
|00006340| 20 20 20 70 72 69 6e 74 | 66 28 22 68 65 61 70 20 |   print|f("heap |
|00006350| 20 20 20 20 20 20 75 73 | 65 72 20 20 20 20 20 20 |      us|er      |
|00006360| 20 73 79 73 74 65 6d 5c | 6e 22 29 3b 0a 58 20 20 | system\|n");.X  |
|00006370| 20 20 20 20 20 20 20 20 | 20 20 20 66 66 6c 75 73 |        |   fflus|
|00006380| 68 28 73 74 64 6f 75 74 | 29 3b 0a 58 20 20 20 20 |h(stdout|);.X    |
|00006390| 20 20 20 20 20 20 20 20 | 20 73 74 61 67 65 20 2b |        | stage +|
|000063a0| 2b 3b 20 74 65 73 74 5f | 73 6f 72 74 5f 66 75 6e |+; test_|sort_fun|
|000063b0| 63 28 68 65 61 70 5f 73 | 6f 72 74 2c 20 6e 2c 20 |c(heap_s|ort, n, |
|000063c0| 31 29 3b 20 62 72 65 61 | 6b 3b 0a 58 20 20 20 20 |1); brea|k;.X    |
|000063d0| 63 61 73 65 20 33 31 3a | 20 73 74 61 67 65 20 2b |case 31:| stage +|
|000063e0| 2b 3b 20 74 65 73 74 5f | 73 6f 72 74 5f 66 75 6e |+; test_|sort_fun|
|000063f0| 63 28 68 65 61 70 5f 73 | 6f 72 74 2c 20 6e 2c 20 |c(heap_s|ort, n, |
+--------+-------------------------+-------------------------+--------+--------+