# sort.pony

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78``` ``````primitive Sort[A: Seq[B] ref, B: Comparable[B] #read] """ Implementation of dual-pivot quicksort. It operates in-place on the provided Seq, using a small amount of additional memory. The nature of the element-realation is expressed via the supplied comparator. (The following is paraphrased from [Wikipedia](https://en.wikipedia.org/wiki/Quicksort).) Quicksort is a common implementation of a sort algorithm which can sort items of any type for which a "less-than" relation (formally, a total order) is defined. On average, the algorithm takes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is rare. Multi-pivot implementations (of which dual-pivot is one) make efficient use of modern processor caches. ## Example program The following takes an reverse-alphabetical array of Strings ("third", "second", "first"), and sorts it in place alphabetically using the default String Comparator. It outputs: > first > second > third ```pony use "collections" actor Main new create(env:Env) => let array = [ "third"; "second"; "first" ] let sorted_array = Sort[Array[String], String](array) for e in sorted_array.values() do env.out.print(e) // prints "first \n second \n third" end ``` """ fun apply(a: A): A^ => """ Sort the given seq. """ try _sort(a, 0, a.size().isize() - 1)? end a fun _sort(a: A, lo: ISize, hi: ISize) ? => if hi <= lo then return end // choose outermost elements as pivots if a(lo.usize())? > a(hi.usize())? then _swap(a, lo, hi)? end (var p, var q) = (a(lo.usize())?, a(hi.usize())?) // partition according to invariant (var l, var g) = (lo + 1, hi - 1) var k = l while k <= g do if a(k.usize())? < p then _swap(a, k, l)? l = l + 1 elseif a(k.usize())? >= q then while (a(g.usize())? > q) and (k < g) do g = g - 1 end _swap(a, k, g)? g = g - 1 if a(k.usize())? < p then _swap(a, k, l)? l = l + 1 end end k = k + 1 end (l, g) = (l - 1, g + 1) // swap pivots to final positions _swap(a, lo, l)? _swap(a, hi, g)? // recursively sort 3 partitions _sort(a, lo, l - 1)? _sort(a, l + 1, g - 1)? _sort(a, g + 1, hi)? fun _swap(a: A, i: ISize, j: ISize) ? => a(j.usize())? = a(i.usize())? = a(j.usize())? ``````