View source for Sorting algorithms/Shell sort/Whitespace

This solution was tested and found to work correctly with the canonical [http://compsoc.dur.ac.uk/whitespace/download.php Haskell interpreter], [https://github.com/hostilefork/whitespacers/tree/master/ruby this Ruby version], and Pavel Shub's glorious [http://pavelshub.com/blog/2010/10/wspace/ C++ implementation]. Most others either failed to run even the simplest of programs, were Windows-only, or else required tiresome setup.

It was observed early on that hard-coding the values to be sorted might rouse suspicion as to whether such an inscrutable program were really doing any sorting; thus it was decided that input would be provided at runtime. This led to the unfortunate discovery that not all of the aforementioned interpreters handle <tt>EOF</tt> in the same way; Haskell and Ruby error out where C++ returns a convenient -1. In the interest of compatibility, the program reads values until a literal -1 is provided; all other negative numbers are permissible and will be sorted appropriately.

A demonstration of the program capable of receiving further test input is available on [http://ideone.com/zVfzfy Ideone].

<lang Whitespace>    

    
 
  
 	
					   	
	   
	  	
   	
	   
 
  

   	
 
     

   	 
 

   	 
	 	  
 
	  		 
 
 
   		
 
  	  		
	  	
	  	 
 
 			 	  	

   	  
 
  	  	  
	  	
		 	 	
 
  	  	  
	  				 	  	 
   	
	   	  	
		 	 	
 
  
  	  	 	
	  						  	  		
	  	
 
 	  

   	 	
 
			    	
	   
 
 		

   		 
 

    

   			
 
 				
 	   	 	 
	
     	
	    
  	  	 
	  	
		 			
 

 


</lang>

While [http://i.imgur.com/8LhJoDG.png semantic highlighting] makes the code slightly less opaque (read: transparent), it's much easier to read the pseudo-Assembly from which it was generated.

<lang asm>; This is used as the index into the heap while reading, after which it
; holds the number of elements to sort. We shall henceforth call him n.
push 0

0:
    dup     ; Storing input is destructive          [n n]
    dup     ; so we dup the index twice.            [n n n]
    inum    ; Read a number into the heap.          [n n]
    load    ; Get it onto the stack.                [n #]
    push 1  ; Detect when -1 is supplied as input   [n # 1]
    add     ; to simulate EOF                       [n #+1]
    jz   1  ; and stop reading.                     [n]
    push 1  ; Otherwise,                            [n 1]
    add     ; increment                             [n+=1]
    jump 0  ; and go again.                         [n]
1:
    dup     ; Initialize h (outermost loop) to  n.  [n h]
    push 0  ; Buffer to enable clean i < n exit.    [n h 0]
2:
    pop     ; Drop that 0 or an extraneous i.       [n h]
    push 2  ; Constant 2-gap because reasons.       [n h 2]
    div     ; h /= 2                                [n h/=2]
    dup     ; Branch checks eat stack.              [n h h]
    jz   6  ; If h is 0, we're all sorted.          [n h]
    dup     ; Initialize i (middle loop) to h.      [n h i]
3:
    dup     ; We need a copy of i to play with.     [n h i i]
    copy 3  ; Get n for i < n check.                [n h i i n]
    sub     ; i is never greater than n, but        [n h i i-n]
    jz   2  ; exit the loop if they're equal.       [n h i]
    dup     ; Loading eats stack and we need i.     [n h i i]
    load    ; k = a[i]                              [n h i k]
    copy 1  ; j = i                                 [n h i k j]
4:
    dup     ; Copy j the first of many times.       [n h i k j j]
    copy 4  ; Grab h from way down there.           [n h i k j j h]
    sub     ; Check first condition.                [n h i k j j-h]
    jn   5  ; j >= h failed, exit loop.             [n h i k j]
    dup     ; Retrieve j and h again; dup would     [n h i k j j]
    copy 4  ; have complicated the stack for 5.     [n h i k j j h]
    sub     ; Prepare for retrieval, then           [n h i k j j-h]
    load    ; grab a[j - h], which we'll call x.    [n h i k j x]
    copy 2  ; Get k to check k < x.                 [n h i k j x k]
    push 1  ; <, not <= so handle the 0 case        [n h i k j x k+1]
    add     ; by incrementing k                     [n h i k j x k+=1]
    sub     ; before subtracting it from x.         [n h i k j x-k]
    jn   5  ; k < x failed, exit loop.              [n h i k j]
    dup     ; Another j.                            [n h i k j j]
    dup     ; Guess which variable we need.         [n h i k j j j]
    copy 5  ; Grab a copy of h                      [n h i k j j j h]
    sub     ; to subtract it from j                 [n h i k j j j-h]
    load    ; to retrive a[j - h]                   [n h i k j j x]
    store   ; and swap it into j, a[j] = a[j - h]   [n h i k j]
    copy 3  ; Grab one more h                       [n h i k j h]
    sub     ; to decrement the loop variable        [n h i k j-=h]
    jump 4  ; and go again.
5:
    swap    ; Prepare for second swap.              [n h i j k]
    store   ; a[j] = k                              [n h i]
    push 1  ; Do the middle loop's afterthought.    [n h i 1]
    add     ; i++                                   [n h i+=1]
    jump 3
6:
    pop     ; It's just you now, n.                 [n]
    push 0  ; A counter so we can print ascending.  [n c]
7:
    dup     ; Need to load and then increment.      [n c c]
    load    ; Grab the next sorted element.         [n c a[c]]
    onum    ; Display it.                           [n c]
    push 10 ; Legibly, of course.                   [n c 10]
    ochr    ; With a newline.                       [n c]
    push 1  ; Increment                             [n c 1]
    add     ; the counter.                          [n c+=1]
    dup     ; We might need it for another run.     [n c c]
    copy 2  ; Load the total                        [n c c n]
    sub     ; and see if we're finished.            [n c c-n]
    jn   7  ; Negative means go again.              [n c]
    pop     ; Otherwise, exit                       [n]
    pop     ; nice and clean.                       []
    exit</lang>