This is the "evlan.org/utility/Sort" module, which implements various sort algorithms, as well as binary search.

# Evlan API - Standard library for the Evlan programming language
# Copyright (C) 2002-2005 Kenton Varda
# <http://www.evlan.org>
#
# (Note:  This license is temporary, and will change to something more
# friendly once I have decided how exactly I want Evlan licensed.)
#
# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License
# as published by the Free Software Foundation; either version
# 2 of the License, or (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
# General Public License for more details.
#
# You should have received a copy of the GNU Library General Public
# License along with this program; if not, write to the Free
# Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
# MA 02111-1307, USA
# ====================================================================

Sort where
   Native = import "(native)"
   Sort = object of
      #Default sort.  The main advantage of quick sort in imperative
      #languages is that it can be done "in-place".  This is not
      #currently possible in Evlan, probably never will be, and
      #probably would not be advantageous anyway since memory
      #allocation is cheap in Evlan.  Therefore, merge sort is the
      #default sort, because merge sort is stable and guaranteed
      #O(n lg n).
      sort = mergeSort
      
      #Generic quickSort.  It is probably better to use
      #median3QuickSort in most cases.
      #
      #Quick sort is NOT stable.  Elements which are "equal" may end
      #up in any order.
      quickSort = (elements, isBefore) => result where
         #Note:  pivot() is defined at the end of this file.
         parts = pivot(Array.getInterval(elements, 1, elements.size),
                       elements[0], isBefore)
         sortedParts = Array.map(parts, part => quickSort(part, isBefore))
         sortedElements = Array.join({sortedParts[0], {elements[0]}, sortedParts[1]})
         result =
            if elements.size <= 1
               then elements
               else sortedElements
      
      #Median-of-three quick sort.  At least, I think this is what
      #"median-of-three" means.  I just sort of guessed that they mean
      #that the pivot point should be chosen as the median of the
      #first, middle, and last elements, see.  Since that would make
      #sense.  Maybe they normally mean to select the three points
      #randomly, but that obviously won't work well in a purely
      #functional language since you would need to provide a random
      #number seed whenever you sorted.
      #
      #Quick sort is NOT stable.  Elements which are "equal" may end
      #up in any order.
      median3QuickSort = (elements, isBefore) =>
         if elements.size <= 1
            then elements
            else result where
               midpoint = Scalar.floor(elements.size/2)
               three = {elements[0], elements[midpoint], elements[elements.size-1]}
               medianIndex =
                  if  not isBefore(three[0], three[1])
                  and not isBefore(three[2], three[0])
                     then 0
                  else if not isBefore(three[2], three[0])
                      and not isBefore(three[1], three[2])
                     then 2
                     else 1
               median = three[medianIndex]
               groups =
                  if medianIndex == 0
                     then pivot(
                        Array.getInterval(elements, 1, elements.size),
                        median, isBefore)
                  else if medianIndex == 2
                     then pivot(
                        Array.getInterval(elements, 0, elements.size-1),
                        median, isBefore)
                     else result where
                        groups0 = pivot(
                           Array.getInterval(elements, 0, midpoint),
                           median, isBefore)
                        groups1 = pivot(
                           Array.getInterval(elements, midpoint+1, elements.size),
                           median, isBefore)
                        result = array of
                           Array.join({groups0[0], groups1[0]})
                           Array.join({groups0[1], groups1[1]})
               resultParts = array of
                  median3QuickSort(groups[0], isBefore)
                  {median}
                  median3QuickSort(groups[1], isBefore)
               result = Array.join(resultParts)
      
      #Using merge sort if you want guaranteed O(n lg n) or if you
      #need a stable sort.  It's generally slower than quickSort,
      #although this is mainly because it keeps producing lists and
      #converting them to arrays.  I think with proper optimizations
      #(which probably require new native code functions) merge sort
      #could be just as fast as quick sort.
      mergeSort = (elements, isBefore) => result where
         result =
            if elements.size <= 1
               then elements
               else loop(elements)
         loop = elements =>
            if elements.size == 1
               then elements
            else merge(0, 0, empty) where
               midpoint = Scalar.floor(elements.size/2)
               array1 = loop(Array.getInterval(elements, 0, midpoint))
               array2 = loop(Array.getInterval(elements, midpoint, elements.size))
               merge = (i, j, list) =>
                  if i == array1.size
                     then if j == array2.size
                        then Array.makeFromReverseList(list)
                        else merge(i, j+1, array2[j]::list)
                  else if j != array2.size and isBefore(array2[j], array1[i])
                     then merge(i, j+1, array2[j]::list)
                     else merge(i+1, j, array1[i]::list)
      
      #An implementation of the bogo-sort algorithm.  This algorithm
      #is designed to be the worst imaginable sorting method, with a
      #time complexity of O(n!).  It works by generating every
      #possible permutation of the array, testing each one to see if
      #it is sorted, and returning the one which is.
      #
      #The usual implementation of bogo-sort chooses permutations
      #randomly.  Unfortunately, due to prohibition of side effects,
      #it would be rather difficult to implement it as such in a
      #purely functional language.  Instead, this implementation
      #searches *all* permutations, not quitting early when it finds
      #the correct result.  (Incidentally, this means the
      #fully-parallel version of this algorithm is O(n), but you'll
      #need O(n!) processors.)
      #
      #Calling bogoSort on anything more than very small arrays is
      #likely to hang your virtual machine.  Even a ten-element array
      #will take quite some time to sort.
      bogoSort = (elements, isBefore) => result where
         initialIndices = Array.make(elements.size, i => i)
         result = permute(initialIndices, empty).value
         
         #recursive function to search the permutation tree...
         permute = (indices, soFar) =>
            if indices.size == 0
               then if check(soFar)
                  then Maybe.make of
                     Array.map(Array.makeFromReverseList(soFar), i => elements[i])
                  else Maybe.empty
               else result where
                  attempts = Array.make(indices.size, subPermute)
                  subPermute = i => permute(subIndices, indices[i]::soFar) where
                     subIndices = Array.join({
                        Array.getInterval(indices, 0, i),
                        Array.getInterval(indices, i+1, indices.size)})
                  findResult = Array.findFirst(attempts, attempt => not attempt.isEmpty)
                  result = attempts[Maybe.default(findResult, 0)]
         #check a particular permutation to see if it's right
         check = indexList =>
            if indexList.isEmpty or indexList.rest.isEmpty
               then true
               else result where
                  i = indexList.first
                  j = indexList.rest.first
                  isInOrder =
                     if isBefore(elements[j], elements[i])
                        then true
                     else if isBefore(elements[i], elements[j])
                        then false
                        else j < i  #enforce stable sort
                  result =
                     if isInOrder
                        then check(indexList.rest)
                        else false
      
      #An implementation of the many-worlds bogo-sort algorithm.  This
      #is the fastest known sorting algorithm, running in O(n) time.
      #Unfortunately, it has some added requirements which make its
      #use impractical in most situations.  Also, since many-worlds
      #bogo-sort depends on side-effecting operations in its
      #execution, it unfortunately must be implemented as a procedure
      #rather than a function.
      #
      #Many-worlds bogo-sort is based on the "Many-Worlds" theory of
      #quantum mechanics.  This theory postulates that every time a
      #random quantum event occurs, the universe actually splits into
      #several parallel timelines, one for each possible outcome of
      #the event.  Many-worlds bogo-sort takes advantage of this by
      #first producing a random permutation of the input array, then
      #destroying any universe in which the permutation turns out not
      #to be sorted.
      #
      #In keeping with Evlan's capability-based security, you must
      #provide an object implementing the current universe.  This
      #object has one required method: a procedure which takes no
      #arguments called destroy().  It is expected that this procedure
      #will not return.
      #
      #You must also provide a procedure getEntropy().  This is
      #similar to the standard getEntropy() procedure provided by the
      #Evlan platform, taking as an argument an integer, and returing
      #an array of that many bytes, randomly generated.  Be careful,
      #though; the procedure you provide must derive its randomness
      #from quantum events, such that every bit string has some
      #probability of being generated (the probabilities need not be
      #equal, however).  Otherwise, if it happens that the bit string
      #representing the correct permutation is impossible to generate,
      #all universes will be destroyed.
      #
      #Please note that this procedure has not been well-tested.
      manyWorldsBogoSort = (elements, isBefore, getEntropy, universe) => do
         entropy := getEntropy(elements.size*4)
         indices = Array.map(Data.formatArray(entropy, 32), Integer.decode)
         checkIndex = i =>
            if indices[i] >= elements.size
               then false
            else if isBefore(elements[indices[i]], elements[indices[i+1]])
               then true
            else if isBefore(elements[indices[i+1]], elements[indices[i]])
               then false
               else indices[i] < indices[i+1] #stable sort
         checkResults = Array.make(elements.size - 1, checkIndex)
         
         if Array.contains(checkResults, b => not b) do
            universe.destroy()
            throw error("universe.destroy() returned.  Universe was not destroyed.")
         
         return Array.map(indices, i => elements[i])
      
      #binarySearch finds the first element in the array for which
      #isBeforeKey evaluates to false, assuming that it returns true
      #for all elements before that point and false for all elements
      #after that point.  If isBeforeKey evaluates to true for all
      #elements in the array, the size of the array is returned.
      #Think of it this way:  binarySearch looks for the edge between
      #the trues and the falses.
      #
      #Of course, this is most useful for finding particular elements
      #in a sorted array.
      binarySearch = (sortedArray, isBeforeKey) => find(0, sortedArray.size) where
         find = (start, end) => result where
            midpoint = Scalar.floor((start + end) / 2)
            result =
               if start == end
                  then start
               else if isBeforeKey(sortedArray[midpoint])
                  then find(midpoint+1, end)
                  else find(start, midpoint)
      
      #Separates repeats from a sorted array.
      separateDuplicates = (sortedArray, areEqual) => result where
         groups = Array.group(sortedArray, 2, groupElement)
         groupElement = i =>
            if not (i == 0) and areEqual(sortedArray[i], sortedArray[i-1])
               then 1 else 0
         result = object of
            unique = groups[0]
            repeated = groups[1]
   
   
   #Private helper used by quickSort.
   pivot = (elements, median, isBefore) => Array.group(elements, 2,
      i => if isBefore(elements[i], median) then 0 else 1)