VB6: Sorting algorithms (sort array, sorting arrays)

[Ellis Dee]

I came up with a new sorting algorithm that is as fast or faster than any other algorithm, including quick sort, and it scales up as well as quicksort excluding memory constraints. It is in the merge sort family, and it is unstable, out-of-place, offline, and non-recursive. I call it snake sort due to its similarity to fantasy football snake drafts.

The idea is simple: A random ordering will result in very small contiguous ordered blocks in either direction. Snake sort begins by identifying all those blocks, and then merges them together. Each merge pass will halve the remaining number of blocks, so it very quickly resolves to a sorted state.

It uses quite a bit of memory; a full copy of the original array, plus an index array (to remember the block cutoffs) of longs half the size of the original array.

Consider the 10 character string SJDFGASLKD. The first three letters, SJD, are already in descending order, so they are the first block. FG are in ascending order, so that's the second block. AS becomes the third block, and LKD (descending order) rounds us out with the fourth and final block.

One key optimization is to bounce the array contents back and forth between the original array and the mirror array instead of merging to the mirror and then copying back to the original each step. This means that if the last step leaves the contents in the mirror, an additional pass must be run to copy that back over the original.

Due to the support of both ascending and descending blocks and the bouncing back and forth between the two arrays -- both of which greatly improve efficiency -- the code sprawl is significant. I've moved the merging code into a separate function to help alleviate this, which means it could still be slightly improved by moving it all into a single function. That optimization would make the code sprawl severe, and likely wouldn't improve sorting times that much.

Here's the debug info I generated in testing for a shuffled array in the graphical screen. Notice how descending blocks are denoted by negative numbers: (Blocks are called levels.)

----------------------
|   Copy to Mirror   |
----------------------
(0)=73...Level(0)=0
(1)=69
(2)=49
(3)=15...Level(1)=-3
(4)=91
(5)=1...Level(2)=-5
(6)=47
(7)=23...Level(3)=-7
(8)=53
(9)=13...Level(4)=-9
(10)=81
(11)=79
(12)=55...Level(5)=-12
(13)=57
(14)=9...Level(6)=-14
(15)=31
(16)=39...Level(7)=16
(17)=7
(18)=33
(19)=63
(20)=97...Level(8)=20
(21)=83
(22)=11...Level(9)=-22
(23)=25
(24)=59
(25)=89...Level(10)=25
(26)=35
(27)=37
(28)=67...Level(11)=28
(29)=3
(30)=21...Level(12)=30
(31)=17
(32)=75...Level(13)=32
(33)=61
(34)=51...Level(14)=-34
(35)=71
(36)=29
(37)=27
(38)=5...Level(15)=-38
(39)=85
(40)=87...Level(16)=40
(41)=41
(42)=95...Level(17)=42
(43)=77
(44)=43...Level(18)=-44
(45)=45
(46)=99...Level(19)=46
(47)=19
(48)=93...Level(20)=48
(49)=65...Level(21)=49
----------------------
|  Copy to Original  |
----------------------
(0)=1...Level(0)=0
(1)=15
(2)=49
(3)=69
(4)=73
(5)=91...Level(1)=5
(6)=13
(7)=23
(8)=47
(9)=53...Level(2)=9
(10)=9
(11)=55
(12)=57
(13)=79
(14)=81...Level(3)=14
(15)=7
(16)=31
(17)=33
(18)=39
(19)=63
(20)=97...Level(4)=20
(21)=11
(22)=25
(23)=59
(24)=83
(25)=89...Level(5)=25
(26)=3
(27)=21
(28)=35
(29)=37
(30)=67...Level(6)=30
(31)=17
(32)=51
(33)=61
(34)=75...Level(7)=34
(35)=5
(36)=27
(37)=29
(38)=71
(39)=85
(40)=87...Level(8)=40
(41)=41
(42)=43
(43)=77
(44)=95...Level(9)=44
(45)=19
(46)=45
(47)=93
(48)=99...Level(10)=48
(49)=65...Level(11)=49
----------------------
|   Copy to Mirror   |
----------------------
(0)=1...Level(0)=0
(1)=13
(2)=15
(3)=23
(4)=47
(5)=49
(6)=53
(7)=69
(8)=73
(9)=91...Level(1)=9
(10)=7
(11)=9
(12)=31
(13)=33
(14)=39
(15)=55
(16)=57
(17)=63
(18)=79
(19)=81
(20)=97...Level(2)=20
(21)=3
(22)=11
(23)=21
(24)=25
(25)=35
(26)=37
(27)=59
(28)=67
(29)=83
(30)=89...Level(3)=30
(31)=5
(32)=17
(33)=27
(34)=29
(35)=51
(36)=61
(37)=71
(38)=75
(39)=85
(40)=87...Level(4)=40
(41)=19
(42)=41
(43)=43
(44)=45
(45)=77
(46)=93
(47)=95
(48)=99...Level(5)=48
(49)=65...Level(6)=49
----------------------
|  Copy to Original  |
----------------------
(0)=1...Level(0)=0
(1)=7
(2)=9
(3)=13
(4)=15
(5)=23
(6)=31
(7)=33
(8)=39
(9)=47
(10)=49
(11)=53
(12)=55
(13)=57
(14)=63
(15)=69
(16)=73
(17)=79
(18)=81
(19)=91
(20)=97...Level(1)=20
(21)=3
(22)=5
(23)=11
(24)=17
(25)=21
(26)=25
(27)=27
(28)=29
(29)=35
(30)=37
(31)=51
(32)=59
(33)=61
(34)=67
(35)=71
(36)=75
(37)=83
(38)=85
(39)=87
(40)=89...Level(2)=40
(41)=19
(42)=41
(43)=43
(44)=45
(45)=65
(46)=77
(47)=93
(48)=95
(49)=99...Level(3)=49
----------------------
|   Copy to Mirror   |
----------------------
(0)=1...Level(0)=0
(1)=3
(2)=5
(3)=7
(4)=9
(5)=11
(6)=13
(7)=15
(8)=17
(9)=21
(10)=23
(11)=25
(12)=27
(13)=29
(14)=31
(15)=33
(16)=35
(17)=37
(18)=39
(19)=47
(20)=49
(21)=51
(22)=53
(23)=55
(24)=57
(25)=59
(26)=61
(27)=63
(28)=67
(29)=69
(30)=71
(31)=73
(32)=75
(33)=79
(34)=81
(35)=83
(36)=85
(37)=87
(38)=89
(39)=91
(40)=97...Level(1)=40
(41)=19
(42)=41
(43)=43
(44)=45
(45)=65
(46)=77
(47)=93
(48)=95
(49)=99...Level(2)=49
----------------------
|  Copy to Original  |
----------------------
(0)=1
(1)=3
(2)=5
(3)=7
(4)=9
(5)=11
(6)=13
(7)=15
(8)=17
(9)=19
(10)=21
(11)=23
(12)=25
(13)=27
(14)=29
(15)=31
(16)=33
(17)=35
(18)=37
(19)=39
(20)=41
(21)=43
(22)=45
(23)=47
(24)=49
(25)=51
(26)=53
(27)=55
(28)=57
(29)=59
(30)=61
(31)=63
(32)=65
(33)=67
(34)=69
(35)=71
(36)=73
(37)=75
(38)=77
(39)=79
(40)=81
(41)=83
(42)=85
(43)=87
(44)=89
(45)=91
(46)=93
(47)=95
(48)=97
(49)=99
----------------------
|   Sort Complete    |
----------------------

Once the initial pass identifies the original blocks, no basic comparisons are needed ever again, since by definition any elements inside a block are already in a sorted order. Each subsequent pass merges two blocks together, so the new block cutoffs are already known. This is another key optimization, which resulted in huge time savings. (Almost doubling the speed.)