Shell Sort Implemented In Go Using Incremental Insertion Sort

shellSort.go

// see https://play.golang.org/p/dB1ELVO8c69
package main

import (
	"fmt"
	"math/rand"
)

const MaxNum = 15

type Node struct {
	Previous *Node
	D        int
	Next     *Node
}

// String is a method displays a node and all it's "next" nodes
func (node Node) String() string {
	str := ""
	cn := &node
	for cn.Next != nil {
		str += fmt.Sprintf("%d -> ", cn.D)
		cn = cn.Next
	}
	str += "nil"
	return str
}

// NewLinkedListOfNodes creates a linked list of 'length' nodes.
func NewLinkedListOfNodes(length int) Node {
	root := Node{
		D: rand.Intn(MaxNum),
	}
	currentNode := &root
	for i := 0; i < length; i++ {
		currentNode.Next = &Node{
			D: rand.Intn(MaxNum),
		}
		currentNode = currentNode.Next
	}
	return root
}

// shellSort creates links to previous nodes and calls incrementalInsertionSort
func (firstNode *Node) shellSort(first, last int) {
	for space := (last - first) / 2; space > 0; space = space / 2 {
		previous, current := firstNode, firstNode
		counter := 0
		fmt.Printf("-----> Before parital sort with space %d : \n", space)
		fmt.Println(firstNode)
		for counter < space && current != nil {
			current = current.Next
			counter++
		}
		for previous != nil && current != nil {
			current.Previous = previous
			current = current.Next
			previous = previous.Next
		}
		firstNode.incrementalInsertionSort(first, last, space)
		fmt.Printf("-----> After parital sort with space %d : \n", space)
		fmt.Println(firstNode)
	}

}

// incrementalInsertionSort does an insertion sort on elements separated by space
func (firstNode *Node) incrementalInsertionSort(first, last, space int) {
	current := firstNode
	for counter := 0; counter < space; counter++ {
		current = current.Next
	}
	for current != nil {
		for c := current; c != nil && c.Previous != nil; c = c.Previous {
			fmt.Printf("-> Comparing %d with %d\n", c.D, c.Previous.D)
			if c.Previous.D > c.D {
				fmt.Printf("-> Swapping %d with %d\n", c.D, c.Previous.D)
				c.D, c.Previous.D = c.Previous.D, c.D // single line swap... in Go we don't use temp
			}
		}
		current = current.Next
	}
}

func main() {
	numNodes := 11
	list := NewLinkedListOfNodes(numNodes)
	list.shellSort(0, numNodes)
}

I fixed an outputting error.