sort.ps

% PostScript Sorting Procedures
% by Raymond Luckhurst, scriptit.uk

% good for small arrays < 100 items
% see http://warp.povusers.org/SortComparison/InsertionSort.txt
/insertionsort {
	exch
	1 1 2 index length 1 sub {
		2 copy get
		1 index -1 1 {
			3 index 1 index 1 sub get
			dup 3 index 7 index exec le { pop exit } if
			4 index exch 2 index exch put
			1 eq { 0 } if
		} for
		3 -1 roll
		1 index ne {
			exch 3 copy put
		} if
		pop pop
	} for
	exch pop
} bind def

% good for almost sorted with random end elements
% see http://warp.povusers.org/SortComparison/ShellSort.txt
/shellsort {
	exch
	dup length % size
	dup 9 idiv % hmax
	1 { 2 copy ge { 3 mul 1 add }{ exit } ifelse } loop % h
	{
		dup 0 gt { % h > 0
			dup 1 4 index 1 sub { % i
				4 index 1 index get % v = a[j]
				1 index 3 index neg 4 index { % j
					6 index 1 index 5 index sub get % a[j-h]
					dup 3 index 10 index exec le { pop exit } if % if a[j-h] <= v
					7 index exch 2 index exch put % a[j] = a[j-h]
					3 index sub % j -= h
					dup 4 index ge { pop } if
				} for
				dup 3 index ne {
					exch 6 index 3 1 roll put % a[j] = v
				}{
					pop pop
				} ifelse
				pop
			} for
			3 idiv % h /= 3
		}{
			exit
		} ifelse
	} loop
	pop pop pop exch pop
} bind def

% fast except for almost sorted with random end elements
% see http://warp.povusers.org/SortComparison/QuickSort.txt
/medianhybridquicksort {
	bind exch
	2 copy length 1 sub 0 _medianhybridquicksort
	exch insertionsort
} bind def

/_medianhybridquicksort { % array proc last first
	{
		% stop when partition size < 16
		2 copy 16 add le {
			pop pop pop
			exit
		} if
		% find median of three
		2 copy add 2 idiv 4 index exch get % v3
		4 index 3 index get % v2
		5 index 3 index get % v1
		2 copy 7 index exec gt { % v2 > v1 ?
			2 index 1 index 7 index exec lt { % v3 < v1 ?
				exch pop exch pop % v1
			}{
				pop 2 copy 6 index exec gt { exch } if pop % min(v2,v3)
			} ifelse
		}{
			2 index 2 index 7 index exec lt { % v3 < v2 ?
				pop exch pop % v2
			}{
				exch pop 2 copy 6 index exec gt { exch } if pop % min(v1,v3)
			} ifelse
		} ifelse
		% sort partition
		2 index 2 index % pivot last first
		{
			{
				6 index 1 index get
				dup 4 index 8 index exec lt { pop 1 add }{ exit } ifelse
			} loop
			3 -1 roll
			{
				7 index 1 index get
				dup 5 index 9 index exec gt { pop 1 sub }{ exit } ifelse
			} loop
			3 index 2 index lt {
				8 index 4 index 2 index put pop
				exch
				7 index 2 index 2 index put pop
				1 sub exch 1 add
			}{
				pop 4 1 roll
				pop pop pop
				exit
			} ifelse
		} loop
		4 index 4 index 2 index 4 index _medianhybridquicksort pop
		1 add exch pop
	} loop
} bind def

% convert dict to array of [key value] pairs sorted by key or value
% <dict> <key?> dsort <array>
/dsort {
	1 index length 0 ne {
		dup 2 index { pop exit } forall type /nametype eq and % true to stringize names
		2 index length array
		0
		5 -1 roll { % get [key value] pairs
			4 index { exch cvas exch } if % cannot compare nametype
			2 array astore
			3 copy put
			pop 1 add
		} forall
		pop
		3 -1 roll {
			{ 0 get exch 0 get exch } medianhybridquicksort % key sort
		}{
			{ 1 get exch 1 get exch } medianhybridquicksort % value sort
		} ifelse
		exch { % restore name keys
			dup { dup 0 get cvn 0 exch put } forall
		} if
	}{
		pop pop 0 array
	} ifelse
} bind def