Quicksort

A pure SQL implementation of QuickSort Algorithm using Recursive CTE expressions, by N. Can KIRIK ( can(at)epati.com.tr )
PS. This implementation, which is heavily resource-hungry, is education purposes only.
Don't use this implementation on production environment, instead use "sort" function of "intarray" contrib package.
----
A status stack used to simulate a function call stack.
This can't be done without a stack due to difference in nature of recursive functionality of CTE expressions.
A custom composite type that uses a custom enum type (direction) to track status ( call stack data type ):
CREATE TYPE "enum_quickSort_direction" AS ENUM ('up', 'down', 'left', 'right');
CREATE TYPE "t_quickSort_status" AS ("direction" "enum_quickSort_direction", "left" int4, "pivot" int4, "right" int4);
----
This shorthand function used to swap elements in an array.
CREATE OR REPLACE FUNCTION "fn_quickSort_swap"( "myArray" _int4, "old" int4, "new" int4) RETURNS _int4 AS $BODY$
SELECT
 CASE
 WHEN $2 = $3 THEN
 $1
 ELSE 
 CASE
 WHEN ARRAY_LOWER( $1, 1 ) <= LEAST( $2, $3 ) - 1 THEN 
 $1[ ARRAY_LOWER( $1, 1 ) : LEAST( $2, $3 ) - 1 ] || $1[ GREATEST( $2, $3 ) ]
 ELSE
 ARRAY[ $1[ GREATEST( $2, $3 ) ] ]
 END
 ||
 CASE
 WHEN $2 != $3 THEN
 $1[ LEAST( $2, $3 ) + 1 : GREATEST( $2, $3 ) - 1 ] || $1[ LEAST( $2, $3 ) ]
 ELSE
 ARRAY[ $1[ LEAST( $2, $3 ) ] ]
 END
 ||
 $1[ GREATEST( $2, $3 ) + 1 : ARRAY_UPPER( $1, 1 ) ]
 END
;
$BODY$ LANGUAGE 'sql' IMMUTABLE;
----
The Partition function, core functionality of QuickSort algorithm, is implemented using recursive CTE's
"t_quickSort_partitionResult" custom composite type used to able to return two different values, which are pivot index and partitioned array.
CREATE TYPE "public"."t_quickSort_partitionResult" AS ( "pivot" int4, "myArray" int4[] );
CREATE OR REPLACE FUNCTION "public"."fn_quickSort_partition"( "myArray" _int4, "left" int4, "right" int4 ) RETURNS "t_quickSort_partitionResult" AS $BODY$
WITH RECURSIVE
 "partition" AS (
 SELECT
 $2 AS i
 ,$2 AS "index"
 ,"fn_quickSort_swap"( $1, ( $2 + $3 ) / 2, $3 ) AS "a"
 WHERE
 $2 < $3
 UNION ALL
 SELECT
 i + 1
 ,"index" + ( "a"[ i ] <= "a"[ $3 ] )::INT
 ,CASE WHEN "a"[ i ] <= "a"[ $3 ] AND i != "index" THEN "fn_quickSort_swap"( "a", i, "index" ) ELSE "a" END
 FROM
 "partition"
 WHERE
 i < $3
 )
SELECT
 ROW(
 "index"
 ,"fn_quickSort_swap"( "a", "index", $3 )
 )::"t_quickSort_partitionResult"
FROM
 "partition"
WHERE
 i = $3
;
$BODY$ LANGUAGE 'sql' IMMUTABLE;
----
Main function, QuickSort, which also implemented using recursive CTE's
CREATE OR REPLACE FUNCTION "fn_quickSort"( _int4 ) RETURNS _int4 AS $BODY$
WITH RECURSIVE
 "sort" AS (
 SELECT
 $1 AS "myArray"
 ,ARRAY[ ROW( 'down', ARRAY_LOWER( $1, 1 ), NULL, ARRAY_UPPER( $1, 1 ) )::"t_quickSort_status" ] AS "status"
 UNION ALL
 SELECT
 "myArray"
 ,CASE 
 WHEN ( "active" )."direction" = 'up' AND ( "previous" )."direction" = 'down' THEN "status"[ 1 : "idx_active" - 2 ]
 WHEN ( "active" )."direction" = 'up' AND ( "previous" )."direction" = 'right' THEN "status"[ 1 : "idx_active" - 2 ] || ROW( 'up', 0, 0, 0 )::"t_quickSort_status"
 WHEN ( "active" )."direction" = 'up' AND ( "previous" )."direction" = 'left' THEN "status"[ 1 : "idx_active" - 2 ] || ROW( 'right', ( "previous" )."left", ( "previous" )."pivot", ( "previous" )."right" )::"t_quickSort_status"
 WHEN "left" < "right" THEN "status" || ROW( 'left', "left", "pivot", "right" )::"t_quickSort_status"
 WHEN ( "active" )."direction" = 'right' THEN "status"[ 1 : "idx_active" - 1 ] || ROW( 'up', 0, 0, 0 )::"t_quickSort_status"
 WHEN ( "active" )."direction" = 'left' THEN "status"[ 1 : "idx_active" - 1 ] || ROW( 'right', ( "active" )."left", ( "active" )."pivot", ( "active" )."right" )::"t_quickSort_status"
 END
 FROM
 (
 SELECT
 ( COALESCE(
 "fn_quickSort_partition"( "myArray", "left", "right" )
 ,ROW( ( "active" )."pivot", "myArray" )::"t_quickSort_partitionResult"
 ) ).*
 ,"left"
 ,"right"
 ,"status"
 ,"idx_active"
 ,"active"
 ,"previous"
 FROM
 (
 SELECT
 "myArray"
 ,CASE ( "active" )."direction"
 WHEN 'up' THEN 0
 WHEN 'down' THEN ( "active" )."left"
 WHEN 'left' THEN ( "active" )."left"
 WHEN 'right' THEN ( "active" )."pivot" + 1
 END AS "left"
 ,CASE ( "active" )."direction"
 WHEN 'up' THEN 0
 WHEN 'down' THEN ( "active" )."right"
 WHEN 'left' THEN ( "active" )."pivot" - 1
 WHEN 'right' THEN ( "active" )."right"
 END AS "right"
 ,"status"
 ,"idx_active"
 ,"active"
 ,"previous"
 FROM
 (
 SELECT
 *
 ,ARRAY_LENGTH( "status", 1 ) AS "idx_active"
 ,"status"[ ARRAY_LENGTH( "status", 1 ) ] AS "active"
 ,"status"[ ARRAY_LENGTH( "status", 1 ) - 1 ] AS "previous"
 FROM
 "sort"
 WHERE
 ARRAY_LENGTH( "status", 1 ) > 0
 ) s
 ) s
 ) s
 )
SELECT
 "myArray"
FROM
 "sort"
WHERE
 "status"[ 1 ] IS NULL
LIMIT 1;
$BODY$ LANGUAGE 'sql' IMMUTABLE;
----
PS. This implementation, which is heavily resource-hungry, is education purposes only.
Don't use this implementation on production environment, instead use "sort" function of "intarray" contrib package.