python3 << 'EOF'
import urllib.request
url = 'https://r.jina.ai/http://rosettacode.org/wiki/Sorting_algorithms/Quicksort'
req = urllib.request.Request(url, headers={'User-Agent': 'Mozilla/5.0'})
with urllib.request.urlopen(req, timeout=20) as response:
    html = response.read().decode('utf-8', errors='ignore')
# Find "## [C++]" which should be section header
idx = html.find('## [C++]')
if idx < 0:
    idx = html.find('## C++')
if idx < 0:
    idx = html.find('C++')
print(f'Found at index: {idx}')
if idx >= 0:
    # Show content after C++ header until next ## header
    end_idx = html.find('## [', idx + 5)
    if end_idx < 0:
        end_idx = html.find('## ', idx + 5)
    content = html[idx:end_idx if end_idx > 0 else idx + 10000]
    print(content)
EOF
Found at index: 1480
C++
29 Clojure
30 COBOL
31 CoffeeScript
32 Common Lisp
33 Cowgol
34 Crystal
35 Curry
36 D
37 Delphi
38 Dart
39 E
40 EasyLang
41 EchoLisp
42 Eero
43 Eiffel
44 Elena
45 Elixir
46 Erlang
47 Emacs Lisp
48 ERRE
49 F#
50 Factor
51 Fe
52 Fexl
53 Forth
54 Fortran
55 FunL
56 Gleam
57 Go
58 Golfscript
59 Haskell
60 Hobbes
61 Hobbes
62 Icon and Unicon
63 IDL
64 Idris
65 Io
66 Isabelle
67 J
68 Jactl
69 Java
Toggle Java subsection
69.1 Imperative
69.2 Functional
70 JavaScript
Toggle JavaScript subsection
70.1 Imperative
70.2 Functional
70.2.1 ES6
70.2.2 ES5
71 Joy
72 jq
73 Julia
74 K
75 Bi-partition
76 Tri-partition
77 Koka
78 Kotlin
79 Lambdatalk
80 Lobster
81 Logo
82 Logtalk
83 Lua
Toggle Lua subsection
83.1 in-place
83.2 non in-place
84 Lucid
85 M2000 Interpreter
Toggle M2000 Interpreter subsection
85.1 Recursive calling Functions
85.2 Recursive calling Subs
85.3 Non Recursive
86 M4
87 Maclisp
88 Maple
89 Mathematica /Wolfram Language
90 MATLAB
91 MAXScript
92 Mercury
Toggle Mercury subsection
92.1 A quicksort that works on linked lists
92.2 A quicksort that works on arrays
93 MiniScript
94 Miranda
95 Modula-2
96 Modula-3
97 Mond
98 MUMPS
99 Nanoquery
100 Nemerle
101 NetRexx
102 Nial
103 Nim
Toggle Nim subsection
103.1 Procedural (in place) algorithm
103.2 Functional (inmmutability) algorithm
104 Nix
105 Oberon-2
106 Objeck
107 Objective-C
108 OCaml
Toggle OCaml subsection
108.1 Declarative and purely functional
108.2 Imperative and in place
109 Octave
110 Oforth
111 Ol
112 ooRexx
113 Oz
114 PARI/GP
115 Pascal
116 PascalABC.NET
117 Perl
118 Phix
119 PHP
120 Picat
Toggle Picat subsection
120.1 Function
120.2 Recursion
121 PicoLisp
122 PL/I
123 Pluto
124 PowerShell
Toggle PowerShell subsection
124.1 First solution
124.2 Another solution
124.3 Yet another solution
125 Prolog
126 Python
127 Qi
128 Quackery
129 R
130 Racket
131 Raku
Toggle Raku subsection
131.1 concurrent implementation
131.2 testing
131.3 benchmarking
132 Red
133 REXX
Toggle REXX subsection
133.1 version 1 quickSort
133.2 Version 2 Elegant
133.3 Version 3 Recursive
133.4 Version 6 Optimized
133.5 Timing all versions
134 Refal
135 Ring
136 RISC-V Assembly
137 RPL
138 Ruby
139 Rust
140 SASL
141 Sather
142 Scala
143 Scheme
Toggle Scheme subsection
143.1 List quicksort
143.2 Vector quicksort (in place)
144 Seed7
145 SETL
146 Sidef
147 Simula
148 Standard ML
149 Swift
150 Symsyn
151 Tailspin
152 Tcl
153 TypeScript
154 UnixPipes
155 Ursala
156 V
157 V (Vlang)
158 Wart
159 Wren
160 XPL0
161 Z80 Assembly
162 Zig
163 zkl
 Toggle the table of contents
Sorting algorithms/Quicksort
Page
Discussion
 English
Read
View source
View history
 Tools
Tools
move to sidebar hide
Actions
Read
View source
View history
Refresh
General
What links here
Related changes
Printable version
Permanent link
Page information
Cite this page
Get shortened URL
Browse properties
Appearance
move to sidebar hide
From Rosetta Code
< Sorting algorithms
Sorting algorithms/Quicksort
You are encouraged to solve this task according to the task description, using any language you may know.

Sorting Algorithm
This is a sorting algorithm.   It may be applied to a set of data in order to sort it.     For comparing various sorts, see compare sorts.   For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts


Heap sort | Merge sort | Patience sort | Quick sort

O(n log2n) sorts
Shell Sort

O(n2) sorts
Bubble sort | Cocktail sort | Cocktail sort with shifting bounds | Comb sort | Cycle sort | Gnome sort | Insertion sort | Selection sort | Strand sort

other sorts
Bead sort | Bogo sort | Common sorted list | Composite structures sort | Custom comparator sort | Counting sort | Disjoint sublist sort | External sort | Jort sort | Lexicographical sort | Natural sorting | Order by pair comparisons | Order disjoint list items | Order two numerical lists | Object identifier (OID) sort | Pancake sort | Quickselect | Permutation sort | Radix sort | Ranking methods | Remove duplicate elements | Sleep sort | Stooge sort | [Sort letters of a string] | Three variable sort | Topological sort | Tree sort

This page uses content from Wikipedia. The original article was at Quicksort. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)




Task

Sort an array (or list) elements using the   quicksort   algorithm.

The elements must have a   strict weak order   and the index of the array can be of any discrete type.

For languages where this is not possible, sort an array of integers.


Quicksort, also known as   partition-exchange sort,   uses these steps.

  Choose any element of the array to be the pivot.
  Divide all other elements (except the pivot) into two partitions.
  All elements less than the pivot must be in the first partition.
  All elements greater than the pivot must be in the second partition.
  Use recursion to sort both partitions.
  Join the first sorted partition, the pivot, and the second sorted partition.


The best pivot creates partitions of equal length (or lengths differing by   1).

The worst pivot creates an empty partition (for example, if the pivot is the first or last element of a sorted array).

The run-time of Quicksort ranges from   O(n log n)   with the best pivots, to   O(n2)   with the worst pivots, where   n   is the number of elements in the array.


This is a simple quicksort algorithm, adapted from Wikipedia.

function quicksort(array)
    less, equal, greater := three empty arrays
    if length(array) > 1
        pivot := select any element of array
        for each x in array
            if x < pivot then add x to less
            if x = pivot then add x to equal
            if x > pivot then add x to greater
        quicksort(less)
        quicksort(greater)
        array := concatenate(less, equal, greater)


A better quicksort algorithm works in place, by swapping elements within the array, to avoid the memory allocation of more arrays.

function quicksort(array)
    if length(array) > 1
        pivot := select any element of array
        left := first index of array
        right := last index of array
        while left ≤ right
            while array[left] < pivot
                left := left + 1
            while array[right] > pivot
                right := right - 1
            if left ≤ right
                swap array[left] with array[right]
                left := left + 1
                right := right - 1
        quicksort(array from first index to right)
        quicksort(array from left to last index)


Quicksort has a reputation as the fastest sort. Optimized variants of quicksort are common features of many languages and libraries. One often contrasts quicksort with   merge sort,   because both sorts have an average time of   O(n log n).

"On average, mergesort does fewer comparisons than quicksort, so it may be better when complicated comparison routines are used. Mergesort also takes advantage of pre-existing order, so it would be favored for using sort() to merge several sorted arrays. On the other hand, quicksort is often faster for small arrays, and on arrays of a few distinct values, repeated many times." — http://perldoc.perl.org/sort.html

Quicksort is at one end of the spectrum of divide-and-conquer algorithms, with merge sort at the opposite end.

Quicksort is a conquer-then-divide algorithm, which does most of the work during the partitioning and the recursive calls. The subsequent reassembly of the sorted partitions involves trivial effort.
Merge sort is a divide-then-conquer algorithm. The partioning happens in a trivial way, by splitting the input array in half. Most of the work happens during the recursive calls and the merge phase.


With quicksort, every element in the first partition is less than or equal to every element in the second partition. Therefore, the merge phase of quicksort is so trivial that it needs no mention!

This task has not specified whether to allocate new arrays, or sort in place. This task also has not specified how to choose the pivot element. (Common ways to are to choose the first element, the middle element, or the median of three elements.) Thus there is a variety among the following implementations.



11l
Translation of: Python
F _quicksort(&array, start, stop) -> Void
   I stop - start > 0
      V pivot = array[start]
      V left = start
      V right = stop
      L left <= right
         L array[left] < pivot
            left++
         L array[right] > pivot
            right--
         I left <= right
            swap(&array[left], &array[right])
            left++
            right--
      _quicksort(&array, start, right)
      _quicksort(&array, left, stop)

F quicksort(&array)
   _quicksort(&array, 0, array.len - 1)

V arr = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0]
quicksort(&arr)
print(arr)
Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

360 Assembly
Translation of: REXX

Structured version with ASM & ASSIST macros.

*        Quicksort                 14/09/2015 & 23/06/2016
QUICKSOR CSECT
         USING  QUICKSOR,R13       base register
         B      72(R15)            skip savearea
         DC     17F'0'             savearea
         STM    R14,R12,12(R13)    prolog
         ST     R13,4(R15)         "
         ST     R15,8(R13)         "
         LR     R13,R15            "
         MVC    A,=A(1)            a(1)=1
         MVC    B,=A(NN)           b(1)=hbound(t)
         L      R6,=F'1'           k=1
       DO WHILE=(LTR,R6,NZ,R6)   do while k<>0    ==================
         LR     R1,R6              k
         SLA    R1,2               ~
         L      R10,A-4(R1)        l=a(k)
         LR     R1,R6              k
         SLA    R1,2               ~
         L      R11,B-4(R1)        m=b(k)
         BCTR   R6,0               k=k-1
         LR     R4,R11             m
         C      R4,=F'2'           if m<2
         BL     ITERATE            then iterate
         LR     R2,R10             l
         AR     R2,R11             +m
         BCTR   R2,0               -1
         ST     R2,X               x=l+m-1
         LR     R2,R11             m
         SRA    R2,1               m/2
         AR     R2,R10             +l
         ST     R2,Y               y=l+m/2
         L      R1,X               x
         SLA    R1,2               ~
         L      R4,T-4(R1)         r4=t(x)
         L      R1,Y               y
         SLA    R1,2               ~
         L      R5,T-4(R1)         r5=t(y)
         LR     R1,R10             l
         SLA    R1,2               ~
         L      R3,T-4(R1)         r3=t(l)
         IF     CR,R4,LT,R3        if t(x)<t(l)       ---+
         IF     CR,R5,LT,R4          if t(y)<t(x)        |
         LR     R7,R4                  p=t(x)            |
         L      R1,X                   x                 |
         SLA    R1,2                   ~                 |
         ST     R3,T-4(R1)             t(x)=t(l)         |
         ELSEIF CR,R5,GT,R3          elseif t(y)>t(l)    |
         LR     R7,R3                  p=t(l)            |
         ELSE   ,                    else                |
         LR     R7,R5                  p=t(y)            |
         L      R1,Y                   y                 |
         SLA    R1,2                   ~                 |
         ST     R3,T-4(R1)            t(y)=t(l)          |
         ENDIF  ,                    end if              |
         ELSE   ,                  else                  |
         IF     CR,R5,LT,R3          if t(y)<t(l)        |
         LR     R7,R3                  p=t(l)            |
         ELSEIF CR,R5,GT,R4          elseif t(y)>t(x)    |
         LR     R7,R4                  p=t(x)            |
         L      R1,X                   x                 |
         SLA    R1,2                   ~                 |
         ST     R3,T-4(R1)             t(x)=t(l)         |
         ELSE   ,                    else                |
         LR     R7,R5                  p=t(y)            |
         L      R1,Y                   y                 |
         SLA    R1,2                   ~                 |
         ST     R3,T-4(R1)             t(y)=t(l)         |
         ENDIF  ,                    end if              |
         ENDIF  ,                  end if             ---+
         LA     R8,1(R10)          i=l+1
         L      R9,X               j=x
FOREVER  EQU    *                  do forever  --------------------+
         LR     R1,R8                i                             |
         SLA    R1,2                 ~                             |
         LA     R2,T-4(R1)           @t(i)                         |
         L      R0,0(R2)             t(i)                          |
         DO WHILE=(CR,R8,LE,R9,AND,  while i<=j and   ---+         |   X
               CR,R0,LE,R7)                t(i)<=p       |         |
         AH     R8,=H'1'               i=i+1             |         |
         AH     R2,=H'4'               @t(i)             |         |
         L      R0,0(R2)               t(i)              |         |
         ENDDO  ,                    end while        ---+         |
         LR     R1,R9                j                             |
         SLA    R1,2                 ~                             |
         LA     R2,T-4(R1)           @t(j)                         |
         L      R0,0(R2)             t(j)                          |
         DO WHILE=(CR,R8,LT,R9,AND,  while i<j and    ---+         |   X
               CR,R0,GE,R7)                t(j)>=p       |         |
         SH     R9,=H'1'               j=j-1             |         |
         SH     R2,=H'4'               @t(j)             |         |
         L      R0,0(R2)               t(j)              |         |
         ENDDO  ,                    end while        ---+         |
         CR     R8,R9                if i>=j                       |
         BNL    LEAVE                then leave (segment finished) |
         LR     R1,R8                i                             |
         SLA    R1,2                 ~                             |
<response clipped><NOTE>Due to the max output limit, only part of the full response has been shown to you.</NOTE>           (* Safely swap two elements of an array. *)
swap_elems_1 {n     : int}
             {i, j  : nat | i <= j; j < n}
             {p     : addr}
             (pfarr : !array_v(a, p, n) >> _ |
              p     : ptr p,
              i     : size_t i,
              j     : size_t j) : void =

  let
    fn {a : vt@ype}
    swap {n     : int}
         {i, j  : nat | i < j; j < n}
         {p     : addr}
         (pfarr : !array_v(a, p, n) >> _ |
          p     : ptr p,
          i     : size_t i,
          j     : size_t j) : void =
      {

        (* Safely swapping linear elements requires that views of
           those elements be split off from the rest of the
           array. Why? Because those elements will temporarily be in
           an uninitialized state. (Actually they will be "?!", but
           the difference is unimportant here.)

           Remember, a linear value is consumed by using it.

           The view for the whole array can be reassembled only after
           new values have been stored, making the entire array once
           again initialized. *)

        prval @(pf1, pf2, pf3) =
          array_v_subdivide3 {a} {p} {i, j - i, n - j} pfarr
        prval @(pfi, pf2_) = array_v_uncons pf2
        prval @(pfj, pf3_) = array_v_uncons pf3

        val pi = ptr_add<a> (p, i)
        and pj = ptr_add<a> (p, j)

        val xi = ptr_get<a> (pfi | pi)
        and xj = ptr_get<a> (pfj | pj)

        val () = ptr_set<a> (pfi | pi, xj)
        and () = ptr_set<a> (pfj | pj, xi)

        prval pf2 = array_v_cons (pfi, pf2_)
        prval pf3 = array_v_cons (pfj, pf3_)
        prval () = pfarr := array_v_join3 (pf1, pf2, pf3)
      }
  in
    if i < j then
      swap {n} {i, j} {p} (pfarr | p, i, j)
    else
      ()   (* i = j must be handled specially, due to linear typing.*)
  end

fn {a : vt@ype}            (* Safely swap two elements of an array. *)
swap_elems_2 {n    : int}
             {i, j : nat | i <= j; j < n}
             (arr  : &array(a, n) >> _,
              i     : size_t i,
              j     : size_t j) : void =
  swap_elems_1 (view@ arr | addr@ arr, i, j)

overload swap_elems with swap_elems_1
overload swap_elems with swap_elems_2
overload swap with swap_elems

fn {a : vt@ype}         (* Safely compare two elements of an array. *)
lt_elems_1 {n     : int}
           {i, j  : nat | i < n; j < n}
           {p     : addr}
           (pfarr : !array_v(a, p, n) |
            p     : ptr p,
            i     : size_t i,
            j     : size_t j) : bool =
  let
    fn
    compare {n     : int}
            {i, j  : nat | i < j; j < n}
            {p     : addr}
            (pfarr : !array_v(a, p, n) |
             p     : ptr p,
             i     : size_t i,
             j     : size_t j,
             gt    : bool) : bool =
      let
        prval @(pf1, pf2, pf3) =
          array_v_subdivide3 {a} {p} {i, j - i, n - j} pfarr
        prval @(pfi, pf2_) = array_v_uncons pf2
        prval @(pfj, pf3_) = array_v_uncons pf3

        val pi = ptr_add<a> (p, i)
        and pj = ptr_add<a> (p, j)

        val retval =
          if gt then
            array_quicksort$lt<a> (pfj, pfi | pj, pi)
          else
            array_quicksort$lt<a> (pfi, pfj | pi, pj)

        prval pf2 = array_v_cons (pfi, pf2_)
        prval pf3 = array_v_cons (pfj, pf3_)
        prval () = pfarr := array_v_join3 (pf1, pf2, pf3)
      in
        retval
      end
  in
    if i < j then
      compare {n} {i, j} {p} (pfarr | p, i, j, false)
    else if j < i then
      compare {n} {j, i} {p} (pfarr | p, j, i, true)
    else
      false
  end

fn {a : vt@ype}         (* Safely compare two elements of an array. *)
lt_elems_2 {n    : int}
           {i, j : nat | i < n; j < n}
           (arr  : &array (a, n),
            i    : size_t i,
            j    : size_t j) : bool =
  lt_elems_1 (view@ arr | addr@ arr, i, j)

overload lt_elems with lt_elems_1
overload lt_elems with lt_elems_2

implement {a}
array_quicksort {n} (arr, n) =
  let
    sortdef index = {i : nat | i < n}
    typedef index (i : int) = [0 <= i; i < n] size_t i
    typedef index = [i : index] index i

    macdef lt = array_quicksort$lt<a>

    fun
    quicksort {i, j  : index}
              (arr   : &array(a, n) >> _,
               first : index i,
               last  : index j) : void =
      if first < last then
        {
          val pivot =
            array_quicksort$select_pivot_index<a> (arr, first, last)

          (* Swap the pivot with the last element. *)
          val () = swap (arr, pivot, last)
          val pivot = last

          fun
          search_rightwards (arr  : &array (a, n),
                             left : index) : index =
            if lt_elems<a> (arr, left, pivot) then
              let
                val () = assertloc (succ left <> n)
              in
                search_rightwards (arr, succ left)
              end
            else
              left

          fun
          search_leftwards (arr   : &array (a, n),
                            left  : index,
                            right : index) : index =
            if right < left then
              right
            else if lt_elems<a> (arr, pivot, right) then
              let
                val () = assertloc (right <> i2sz 0)
              in
                search_leftwards (arr, left, pred right)
              end
            else
              right

          fun
          partition (arr    : &array (a, n) >> _,
                     left0  : index,
                     right0 : index) : @(index, index) =
            let
              val left = search_rightwards (arr, left0)
              val right = search_leftwards (arr, left, right0)
            in
              if left <= right then
                let
                  val () = assertloc (succ left <> n)
                  and () = assertloc (right <> i2sz 0)
                in
                  swap (arr, left, right);
                  partition (arr, succ left, pred right)
                end
              else
                @(left, right)
            end

          val @(left, right) = partition (arr, first, pred last)

          val () = quicksort (arr, first, right)
          and () = quicksort (arr, left, last)
        }
  in
    if i2sz 2 <= n then
      quicksort {0, n - 1} (arr, i2sz 0, pred n)
  end

(*------------------------------------------------------------------*)

implement
array_quicksort$lt<Strptr1> (pfx, pfy | px, py) =
  compare (!px, !py) < 0

implement
array_quicksort$select_pivot_index<Strptr1> {n} (arr, first, last) =
  (* Median of three. *)
  let
    val middle = first + ((last - first) / i2sz 2)
  in
    if lt_elems<Strptr1> (arr, middle, first)
          xor lt_elems<Strptr1> (arr, last, first) then
      first
    else if lt_elems<Strptr1> (arr, middle, first)
              xor lt_elems<Strptr1> (arr, middle, last) then
      middle
    else
      last
  end

implement
list_vt_map$fopr<string><Strptr1> (s) = string0_copy s

implement
list_vt_freelin$clear<Strptr1> (x) = strptr_free x

implement
main0 () =
  let
    val example_strings =
      $list_vt
        ("choose", "any", "element", "of", "the", "array",
         "to", "be", "the", "pivot",
         "divide", "all", "other", "elements", "except",
         "the", "pivot", "into", "two", "partitions",
         "all", "elements", "less", "than", "the", "pivot",
         "must", "be", "in", "the", "first", "partition",
         "all", "elements", "greater", "than", "the", "pivot",
         "must", "be", "in", "the", "second", "partition",
         "use", "recursion", "to", "sort", "both", "partitions",
         "join", "the", "first", "sorted", "partition", "the",
         "pivot", "and", "the", "second", "sorted", "partition")

    val example_strptrs =
      list_vt_map<string><Strptr1> (example_strings)

    prval () = lemma_list_vt_param example_strptrs
    val n = length example_strptrs

    val @(pf, pfgc | p) = array_ptr_alloc<Strptr1> (i2sz n)
    macdef arr = !p

    val () = array_initize_list_vt<Strptr1> (arr, n, example_strptrs)
    val () = array_quicksort<Strptr1> (arr, i2sz n)
    val sorted_strptrs = array2list (arr, i2sz n)

    fun
    print_strptrs {n       : nat} .<n>.
                  (strptrs : !list_vt (Strptr1, n),
                   i       : int) : void =
      case+ strptrs of
      | NIL => if i <> 1 then println! () else ()
      | @ head :: tail =>
        begin
          print! head;
          if i = 8 then
            begin
              println! ();
              print_strptrs (tail, 1)
            end
          else
            begin
              print! " ";
              print_strptrs (tail, succ i)
            end;
          fold@ strptrs
        end
  in
    println! (length example_strings);
    println! (length sorted_strptrs);
    print_strptrs (sorted_strptrs, 1);
    list_vt_freelin<Strptr1> sorted_strptrs;
    array_ptr_free (pf, pfgc | p);
    list_vt_free<string> example_strings
  end

(*------------------------------------------------------------------*)
Output:
$ patscc -O3 -DATS_MEMALLOC_LIBC quicksort_task_for_arrays_2.dats
62
62
all all all and any array be be
be both choose divide element elements elements elements
except first first greater in in into join
less must must of other partition partition partition
partition partitions partitions pivot pivot pivot pivot pivot
recursion second second sort sorted sorted than than
the the the the the the the the
the the to to two use
A stable quicksort working on linear lists

See the code at the quickselect task.

Output:
$ patscc -O3 -DATS_MEMALLOC_LIBC quickselect_task_for_list_vt.dats && ./a.out quicksort
stable sort by first character:
duck, deer, dolphin, elephant, earwig, giraffe, pronghorn, wildebeest, woodlouse, whip-poor-will
AutoHotkey

Translated from the python example:

a := [4, 65, 2, -31, 0, 99, 83, 782, 7]
for k, v in QuickSort(a)
        Out .= "," v
MsgBox, % SubStr(Out, 2)
return

QuickSort(a)
{
        if (a.MaxIndex() <= 1)
                return a
        Less := [], Same := [], More := []
        Pivot := a[1]
        for k, v in a
        {
                if (v < Pivot)
                        less.Insert(v)
                else if (v > Pivot)
                        more.Insert(v)
                else
                        same.Insert(v)
        }
        Less := QuickSort(Less)
        Out := QuickSort(More)
        if (Same.MaxIndex())
                Out.Insert(1, Same*) ; insert all values of same at index 1
        if (Less.MaxIndex())
                Out.Insert(1, Less*) ; insert all values of less at index 1
        return Out
}


Old implementation for AutoHotkey 1.0:

MsgBox % quicksort("8,4,9,2,1")

quicksort(list)
{
  StringSplit, list, list, `,
  If (list0 <= 1)
    Return list
  pivot := list1
  Loop, Parse, list, `,
  {
    If (A_LoopField < pivot)
      less = %less%,%A_LoopField%
    Else If (A_LoopField > pivot)
      more = %more%,%A_LoopField%
    Else
      pivotlist = %pivotlist%,%A_LoopField%
  }
  StringTrimLeft, less, less, 1
  StringTrimLeft, more, more, 1
  StringTrimLeft, pivotList, pivotList, 1
  less := quicksort(less)
  more := quicksort(more)
  Return less . pivotList . more
}

AWK
# the following qsort implementation extracted from:
#
#       ftp://ftp.armory.com/pub/lib/awk/qsort
#
# Copyleft GPLv2 John DuBois
#
# @(#) qsort 1.2.1 2005-10-21
# 1990 john h. dubois iii (john@armory.com)
#
# qsortArbIndByValue(): Sort an array according to the values of its elements.
#
# Input variables:
#
# Arr[] is an array of values with arbitrary (associative) indices.
#
# Output variables:
#
# k[] is returned with numeric indices 1..n.  The values assigned to these
# indices are the indices of Arr[], ordered so that if Arr[] is stepped
# through in the order Arr[k[1]] .. Arr[k[n]], it will be stepped through in
# order of the values of its elements.
#
# Return value: The number of elements in the arrays (n).
#
# NOTES:
#
# Full example for accessing results:
#
#       foolist["second"] = 2;
#       foolist["zero"] = 0;
#       foolist["third"] = 3;
#       foolist["first"] = 1;
#
#       outlist[1] = 0;
#       n = qsortArbIndByValue(foolist, outlist)
#
#       for (i = 1; i <= n; i++) {
#               printf("item at %s has value %d\n", outlist[i], foolist[outlist[i]]);
#       }
#      delete outlist;
#
function qsortArbIndByValue(Arr, k,
                            ArrInd, ElNum)
{
        ElNum = 0;
        for (ArrInd in Arr) {
                k[++ElNum] = ArrInd;
        }
        qsortSegment(Arr, k, 1, ElNum);
        return ElNum;
}
#
# qsortSegment(): Sort a segment of an array.
#
# Input variables:
#
# Arr[] contains data with arbitrary indices.
#
# k[] has indices 1..nelem, with the indices of Arr[] as values.
#
# Output variables:
#
# k[] is modified by this function.  The elements of Arr[] that are pointed to
# by k[start..end] are sorted, with the values of elements of k[] swapped
# so that when this function returns, Arr[k[start..end]] will be in order.
#
# Return value: None.
#
function qsortSegment(Arr, k, start, end,
                      left, right, sepval, tmp, tmpe, tmps)
{
        if ((end - start) < 1) {        # 0 or 1 elements
                return;
        }
        # handle two-element case explicitly for a tiny speedup
        if ((end - start) == 1) {
                if (Arr[tmps = k[start]] > Arr[tmpe = k[end]]) {
                        k[start] = tmpe;
                        k[end] = tmps;
                }
                return;
        }
        # Make sure comparisons act on these as numbers
        left = start + 0;
        right = end + 0;
        sepval = Arr[k[int((left + right) / 2)]];
        # Make every element <= sepval be to the left of every element > sepval
        while (left < right) {
                while (Arr[k[left]] < sepval) {
                        left++;
                }
                while (Arr[k[right]] > sepval) {
                        right--;
                }
                if (left < right) {
                        tmp = k[left];
                        k[left++] = k[right];
                        k[right--] = tmp;
                }
        }
        if (left == right)
                if (Arr[k[left]] < sepval) {
                        left++;
                } else {
                        right--;
                }
        if (start < right) {
                qsortSegment(Arr, k, start, right);
        }
        if (left < end) {
                qsortSegment(Arr, k, left, end);
        }
}

BASIC
ANSI BASIC
Works with: Decimal BASIC
100 REM Sorting algorithms/Quicksort
110 DECLARE EXTERNAL SUB QuickSort
120 DIM Arr(0 TO 19)
130 LET A = LBOUND(Arr)
140 LET B = UBOUND(Arr)
150 RANDOMIZE
160 FOR I = A TO B
170    LET Arr(I) = ROUND(INT(RND * 99))
180 NEXT I
190 PRINT "Unsorted:"
200 FOR I = A TO B
210    PRINT USING "
[The command completed with exit code 0.]
[Current working directory: /workspace]
[Python interpreter: /usr/local/bin/python]
[Command finished with exit code 0]