sort.go

// Read lines from a bunch of files given on the command line
// and write them out in sorted order, like Unix sort(1).
//
// Written by Lars Buitinck, 2012.
// This code is in the public domain.

package main

import (
    "bufio"
    "flag"
    "fmt"
    "io"
    "os"
    "runtime"
)

type link struct {
    s    string
    next *link
}

func main() {
    runtime.GOMAXPROCS(runtime.NumCPU())
    flag.Parse()

    var list *link = nil

    if flag.NArg() == 0 {
        list = read(os.Stdin, nil)
    } else {
        for i := 0; i < flag.NArg(); i++ {
            arg := flag.Arg(i)
            if arg == "-" {
                list = read(os.Stdin, list)
            } else {
                f, err := os.Open(arg)
                if err != nil { panic(err) }
                defer f.Close()

                list = read(f, list)
            }
        }
    }

    for list = sort(list); list != nil; list = list.next {
        fmt.Print(list.s)
    }
}

// Read lines from r and prepend them to list.
func read(r io.Reader, list *link) *link {
    for f := bufio.NewReader(r);; {
        ln, err := f.ReadString('\n')
        if err == io.EOF {
            break
        } else if err != nil {
            panic(err)
        }
        list = &link{ln, list}
    }
    return list
}

func sort(list *link) *link {
    cpus := runtime.GOMAXPROCS(0)
    ch := make(chan *link, 1)
    parsort(list, ch, cpus)
    return <-ch
}

// Parallel merge sort.
func parsort(list *link, out chan *link, ncpu int) {
    if list == nil || list.next == nil {
        out <- list
        return
    } else if ncpu < 2 {
        out <- seqsort(list)
        return
    }
    a, b := split(list)
    ch1 := make(chan *link)
    ch2 := make(chan *link)
    go parsort(a, ch1, ncpu / 2)
    go parsort(b, ch2, ncpu / 2)
    out <- merge(<-ch1, <-ch2)
}

// Sequential merge sort.
func seqsort(list *link) *link {
    if list == nil || list.next == nil {
        return list
    }
    a, b := split(list)
    a, b = seqsort(a), seqsort(b)
    return merge(a, b)
}

// Split list into two halves, destructively.
func split(list *link) (a, b *link) {
    a, b = new(link), new(link)
    atail, btail := a, b

    for even := true; list != nil; even = !even {
        next := list.next
        if even {
            atail.next = list
            atail = list
        } else {
            btail.next = list
            btail = list
        }
        list = next
    }
    atail.next, btail.next = nil, nil
    a, b = a.next, b.next
    return
}

// Merge two sorted lists, destructively.
func merge(a, b *link) *link {
    head := new(link)
    tail := head

    for a != nil && b != nil {
        if a.s <= b.s {
            tail.next = a
            a = a.next
        } else {
            tail.next = b
            b = b.next
        }
        tail = tail.next
    }
    if a == nil {
        tail.next = b
    } else {
        tail.next = a
    }
    return head.next
}