# Bottom up mergesort - singly linked list

I have written the following program in Go to mergesort a singly linked list. It does bottom up merge sort and hence does not have to find the mid of the linked list. Please review the algorithm and the code for idiomatic Go.

package main

import (
"fmt"
)

type node struct {
val  int
next *node
}

type list struct {
}

func newList(arr []int) *list {

if arr == nil || len(arr) == 0 {
return nil
}
l := new(list)
for i := 1; i < len(arr); i++ {
n := getNode(arr[i])
prev.next = n
prev = n
}

return l
}

func printList(n *node) {
for p := n; p != nil; p = p.next {
fmt.Printf("%d ", p.val)
}
}

func getNode(v int) *node {
n := new(node)
n.val = v
return n
}

func skip(n *node, len int) (fast *node, slow *node) {

counter := 0
fast = n
slow = n
for counter < len {
if fast != nil && fast.next != nil {
fast = fast.next.next
} else if fast != nil {
fast = fast.next
}

if slow != nil {
slow = slow.next
}

counter++
}

return fast, slow

}

func (l *list) mergesort() {

// compare 0,with 1, 2 with 3
// skip n.next.next for next bunch

sublen := 1
len := 0
counted := false

for !counted || sublen < len {
for n := l.head; n != nil; {
fast, slow := skip(n, sublen)

merge(n, slow, sublen)

if !counted {
len += 2
}
n = fast
}
counted = true
sublen += sublen
}
}

func merge(p *node, q *node, len int) {

i := p

if q == nil {
// nothing to merge, return
return
}

j := q
ilen := 0
jlen := 0

var prev *node
var end *node
var penult *node

for (i != q && ilen < len) && (j != nil && jlen < len) {

if i.val < j.val {
n := getNode(i.val)
i = i.next
penult = prev
prev = n
ilen++
} else {
n := getNode(j.val)
setEnd(&end, j, jlen, len)
j = j.next
penult = prev
prev = n
jlen++
}
}

for i != q && ilen < len {
n := getNode(i.val)
i = i.next
penult = prev
prev = n
ilen++
}
for j != nil && jlen < len {
n := getNode(j.val)
setEnd(&end, j, jlen, len)
j = j.next
penult = prev
prev = n
jlen++
}

// replace into original list
end.val = prev.val

// do we have any nodes between head and new end (prev) or is it just the
// two nodes (head and new end (prev)?
penult.next = end
}
}

func setEnd(end **node, n *node, partlen int, len int) {

if n.next != nil && partlen < len-1 {
*end = n.next
} else {
*end = n
}
}

func append(n *node, head **node, prev **node) {

*prev = n
} else {
(*prev).next = n
}
}

func main() {

l := newList([]int{10, 4, 2, 15, 8, 9, 12, 1, 6})
fmt.Println("Original: ")
l.mergesort()
fmt.Println("\nSorted:")

}


Also shared here

• You already state that the code is in Go, so there's no reason to remove this tag. A language tag is required. Aug 11, 2015 at 6:12

Just some random notes:

l := new(list)


This is usually spelled l := &list{head: getNode(arr[0])}.

n := new(node)
n.val = v


Again, can be shortened to n := &node{val: v}.

var head *node
var prev *node
var end *node
var penult *node


Shorten to var head, prev, end, penult *node.

func append


This is a very bad name for a function because it clashes with a built-in. Better change to something like appendList or make it a method.