GoLang - Insertion Sort Implimentaion w/ google go

This article will discuss a simple insertion sort algorithm in golang (google go).
See ALL golang interest postings   |  Insertion Sort By Language Java Scala Go Python Perl

Overview of the Insertion Sort Algorithm
Insertion sort is one of the most natural wayTs of sorting a collection of comparable items.  The reason it is one of the most natural ways is because it is the way most people will sort physical items.   For example each year (about this time) I will sort all 12 of my previous years phone bills, gas bills, etc...  The algorithm used to sort them is to place the first one in stack.  Then the second one is compared to the first one to see if it goes in front of or behind the first one.  The third one is then compared to each if the two sorted items to determine where it fits in.  This procedure continues until all 12 bills are in the pile.  Once all 12 bills are in the pile it is sorted. I happen to sort form oldest to newest, my spouse does it the other way newest to oldest.

Applying this concept to a collection of objects in a computer is fundamentally the same.  The algorithm dictates that one will iterate over a collection of elements in an unsorted list 1 at a time, and place that item into it's correct location in a sorted list.

If the collection of objects to sort is n, insertion sort will take at most $O(n^2)$ operations to perform the sort, it will take on average $\frac{1}{2} O(n^2) = O(n^2)$, and in the best case senario will take $O(n)$ operations.


Questions:  


1.  What would be the initial characteristics of a list that took the worst case order $O(n^2)$ to sort?
2.  What would be the initial characteristics of a list that took the best case order $O(n)$ to sort?


About the GoLang Solution:
Inline comments have been added to the code to discuss some of the syntax and code structure.
If you have a question about the solution (or feel it should be improved) please leave a comment.  All comments are moderated and posted with your name/Identification so please be professional and straight forward.
GoLang Solution:

package main

/*------------------------------------------------------------------------------
  Copyright (c) 2011 ecocrypt.com

  Licensed under the Apache License, Version 2.0 (the "License");
  you may not use this file except in compliance with the License.
  You may obtain a copy of the License at

      http://www.apache.org/licenses/LICENSE-2.0

  Unless required by applicable law or agreed to in writing, software
  distributed under the License is distributed on an "AS IS" BASIS,
  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  See the License for the spe\]cific language governing permissions and
  limitations under the License.
-----------------------------------------------------------------------------*/
import fmt "fmt"  
import "container/list" 
import "rand"

//  The main entry point.
func main() {
    // create a list of integers randomly ordered.
    var  randomOrderedList = createRandomUnsortedList() 

    //  Perform the insertion sort.
    //  return a new sorted list.
    var sortedList = insertionSort(randomOrderedList)


    //  display the list to standard out.
    displayListToStandardOut(sortedList) 

}


//  private function takes unsortedList, returns sortedList
func insertionSort(unsortedList *list.List) (sortedList *list.List){
    sortedList = list.New()
    for e :=unsortedList.Front();e!=nil; e=e.Next() {
        var found = 0
        for s := sortedList.Front();s!=nil;s=s.Next(){
            if(e.Value.(int)>s.Value.(int)){
                found=1
                sortedList.InsertBefore(e.Value,s)
                s=sortedList.Back()
            }
        }
        if(found==0){
            sortedList.PushBack(e.Value)
        }
    }
    return sortedList
}


//  private method displays the lList to standard out.
func displayListToStandardOut(lList *list.List) {
    counter := 0
    for y :=lList.Front();y!=nil; y=y.Next() {
        counter += 1
        fmt.Printf("%d -> %d\n",counter,y.Value)
    }
}

// private method returns lList
func createRandomUnsortedList() (lList *list.List) {
    //  Create a New Random Generator from a Random Source
    //  with a seed of 10.
        var r = rand.New(rand.NewSource(10))

    //  create a list of random integers.
    lList = list.New()
    for i :=0; i<15; i=i + 1 {
        lList.PushFront(r.Int())
    }
    return lList
}

Answers: 1.  The best case senario would be order: $O(n)$ 2.  The worst case senario would be order: $O(n^{2})$golang postings

Go Lang - Hello World

Starting a new language the first example is always Hello World.  Getting going with go-lang is only slightly different.  As of this writing, the current state of 'go-lang' is that you have to build the compiler first, and then write compile and run Hello World.  On UNIX/Linux you can do that pretty easily based on the instructions maintained on the golang.org website.  On windows the GOMINGW  seems to be maintaining good binary compatible version of go built with the mingw compiler collection on windows.

Step 1 Set your environment variables:

E.G. On my windows box I set:

set GOROOT=C:\golang\go
set GOOS=windows
set GOARCH=386

  (look in $GOROOT/pkg for applicable architecture and OS Options)

Step 2 Create a source file in the go language (a go source file):
Use a text editor or write a golang source file:
Sample Hello World GO Language source file:
________________________SOURCE FILE________________________________________


package main

import fmt "fmt"  // Package implementing formatted I/O.

func main() {
      fmt.Printf("Hello, world; from go to ecocrypt.blogspot.com \n")
}

________________________END SOURCE_________________________________________

Save this file to helloworld.go or any filename of your choice.

Step 3  Compile
prompt % 8g helloworld.go

Step 4 Link
prompt % 8l helloworld.go

Step 5 Run the newly created executable:
prompt % 8.out
Hello, world; from go to ecocrypt.blogspot.com

Congratulate Yourself!  You have created and run Hello World in Go.
You should now have a Go compiler successfully installed on your computer.


SOME COMMON ERRORS:
Using the wrong executable to compile go source:
prompt %  8c.exe helloworld.go

helloworld.go:1 not a function
helloworld.go:1 syntax error, last name: main

     This Error is caused because you are trying to compile a go source file with a c compiler.  8c is a c compiler embedded in the go distribution package.

Using the wrong architecture or os settings:

prompt % 8g.exe helloworld.go

helloworld.go:3: can't find import: fmt

Make sure you have set the go environment variables correctly:
Determining the GOOS, and GOARCH can be tricky, you will have to look in:
$GOROOT/pkg/
and there will be a directory of format $GOOS_$ARCH

E.G. On my windows box I set:

set GOROOT=C:\golang\go
set GOOS=windows
set GOARCH=386