1// Copyright 2013 The Go Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style 3// license that can be found in the LICENSE file. 4 5// +build !go1.2 6 7package language 8 9import "sort" 10 11func sortStable(s sort.Interface) { 12 ss := stableSort{ 13 s: s, 14 pos: make([]int, s.Len()), 15 } 16 for i := range ss.pos { 17 ss.pos[i] = i 18 } 19 sort.Sort(&ss) 20} 21 22type stableSort struct { 23 s sort.Interface 24 pos []int 25} 26 27func (s *stableSort) Len() int { 28 return len(s.pos) 29} 30 31func (s *stableSort) Less(i, j int) bool { 32 return s.s.Less(i, j) || !s.s.Less(j, i) && s.pos[i] < s.pos[j] 33} 34 35func (s *stableSort) Swap(i, j int) { 36 s.s.Swap(i, j) 37 s.pos[i], s.pos[j] = s.pos[j], s.pos[i] 38} 39