diff --git a/encode.go b/encode.go
index c4aee87..fa3ebc6 100644
--- a/encode.go
+++ b/encode.go
@@ -5,6 +5,7 @@
 
 import (
 	"reflect"
+	"sort"
 	"strconv"
 	"unsafe"
 )
@@ -126,7 +127,9 @@
 
 func (e *encoder) mapv(tag string, in reflect.Value) {
 	e.mappingv(tag, func() {
-		for _, k := range in.MapKeys() {
+		keys := keyList(in.MapKeys())
+		sort.Sort(keys)
+		for _, k := range keys {
 			e.marshal("", k)
 			e.marshal("", in.MapIndex(k))
 		}
diff --git a/encode_test.go b/encode_test.go
index 50bd9bb..79365fc 100644
--- a/encode_test.go
+++ b/encode_test.go
@@ -1,10 +1,11 @@
 package goyaml_test
 
 import (
+	"fmt"
 	. "launchpad.net/gocheck"
 	"launchpad.net/goyaml"
 	"math"
-	//"reflect"
+	"strings"
 )
 
 var marshalIntTest = 123
@@ -171,3 +172,53 @@
 	c.Assert(err, IsNil)
 	c.Assert(string(data), Equals, "hello: world!\n")
 }
+
+func (s *S) TestSortedOutput(c *C) {
+	order := []interface{}{
+		1,
+		1.0,
+		1.1,
+		1.2,
+		2,
+		2.0,
+		2.1,
+		"a!10",
+		"a/2",
+		"a/10",
+		"a~10",
+		"ab/1",
+		"b/1",
+		"b/01",
+		"b/2",
+		"b/02",
+		"b/3",
+		"b/03",
+		"b1",
+		"b01",
+		"b3",
+		"c2.10",
+		"c10.2",
+		"d1",
+		"d12",
+		"d12a",
+	}
+	m := make(map[interface{}]int)
+	for _, k := range order {
+		m[k] = 1
+	}
+	data, err := goyaml.Marshal(m)
+	c.Assert(err, IsNil)
+	out := "\n" + string(data)
+	last := 0
+	for i, k := range order {
+		repr := fmt.Sprint(k)
+		index := strings.Index(out, "\n"+repr+":")
+		if index == -1 {
+			c.Fatalf("%#v is not in the output: %#v", k, out)
+		}
+		if index < last {
+			c.Fatalf("%#v was generated before %#v: %q", k, order[i-1], out)
+		}
+		last = index
+	}
+}
diff --git a/sorter.go b/sorter.go
new file mode 100644
index 0000000..8a46bef
--- /dev/null
+++ b/sorter.go
@@ -0,0 +1,104 @@
+package goyaml
+
+import (
+	"reflect"
+	"unicode"
+)
+
+type keyList []reflect.Value
+
+func (l keyList) Len() int { return len(l) }
+func (l keyList) Swap(i, j int) { l[i], l[j] = l[j], l[i] }
+func (l keyList) Less(i, j int) bool {
+	a := l[i]
+	b := l[j]
+	ak := a.Kind()
+	bk := b.Kind()
+	for (ak == reflect.Interface || ak == reflect.Ptr) && !a.IsNil() {
+		a = a.Elem()
+		ak = a.Kind()
+	}
+	for (bk == reflect.Interface || bk == reflect.Ptr) && !b.IsNil() {
+		b = b.Elem()
+		bk = b.Kind()
+	}
+	af, aok := keyFloat(a)
+	bf, bok := keyFloat(b)
+	if aok && bok {
+		if af != bf {
+			return af < bf
+		}
+		if ak != bk {
+			return ak < bk
+		}
+		return numLess(a, b)
+	}
+	if ak != reflect.String || bk != reflect.String {
+		return ak < bk
+	}
+	ar, br := []rune(a.String()), []rune(b.String())
+	for i := 0; i < len(ar) && i < len(br); i++ {
+		if ar[i] == br[i] {
+			continue
+		}
+		al := unicode.IsLetter(ar[i])
+		bl := unicode.IsLetter(br[i])
+		if al && bl {
+			return ar[i] < br[i]
+		}
+		if al || bl {
+			return bl
+		}
+		var ai, bi int
+		var an, bn int64
+		for ai = i; ai < len(ar) && unicode.IsDigit(ar[ai]); ai++ {
+			an = an*10 + int64(ar[ai]-'0')
+		}
+		for bi = i; bi < len(br) && unicode.IsDigit(br[bi]); bi++ {
+			bn = bn*10 + int64(br[bi]-'0')
+		}
+		if an != bn {
+			return an < bn
+		}
+		if ai != bi {
+			return ai < bi
+		}
+		return ar[i] < br[i]
+	}
+	return len(ar) < len(br)
+}
+
+// keyFloat returns a float value for v if it is a number/bool
+// and whether it is a number/bool or not.
+func keyFloat(v reflect.Value) (f float64, ok bool) {
+	switch v.Kind() {
+	case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
+		return float64(v.Int()), true
+	case reflect.Float32, reflect.Float64:
+		return v.Float(), true
+	case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
+		return float64(v.Uint()), true
+	case reflect.Bool:
+		if v.Bool() {
+			return 1, true
+		}
+		return 0, true
+	}
+	return 0, false
+}
+
+// numLess returns whether a < b.
+// a and b must necessarily have the same kind.
+func numLess(a, b reflect.Value) bool {
+	switch a.Kind() {
+	case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
+		return a.Int() < b.Int()
+	case reflect.Float32, reflect.Float64:
+		return a.Float() < b.Float()
+	case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
+		return a.Uint() < b.Uint()
+	case reflect.Bool:
+		return !a.Bool() && b.Bool()
+	}
+	panic("not a number")
+}