Natural Sort in SQL
To sort strings in SQL is fairly straightforward:
select * from mytable order by name;This uses the default collation which is at its core based on a character-by-character comparison, which almost always matches what humans would consider to be the “right” order – unless decimal numbers are found, in which case this will sort strings like ‘abc-2000’ before ‘abc-30’.
Natural Sort, on the other hand, compares strings using a more complex algorithm that finds embedded decimal numbers and sorts them according to their numeric value.
I’ve taken the algorithm from https://github.com/sourcefrog/natsort and implemented it in PL/SQL:
create or replace type natural_sort as object (
v varchar2(32767),
order member function compare(p_other natural_sort) return integer
);
/
create or replace type body natural_sort as
order member function compare(p_other natural_sort) return integer is
function is_whitespace(a in char) return boolean is
begin
return a is not null and ascii(a) <= 32;
end is_whitespace;
function is_digit(a in char) return boolean is
begin
return a is not null and ascii(a) between 48 and 57;
end is_digit;
function compare_right(a in varchar2, b in varchar2) return number is
bias number := 0;
ia number := 0;
ib number := 0;
ca char(1 char);
cb char(1 char);
begin
-- The longest run of digits wins. That aside, the greatest
-- value wins, but we can't know that it will until we've scanned
-- both numbers to know that they have the same magnitude, so we
-- remember it in bias.
loop
ca := substr(a, ia, 1);
cb := substr(b, ib, 1);
pragma inline (is_digit, 'yes');
if not is_digit(ca) and not is_digit(cb) then
return bias;
pragma inline (is_digit, 'yes');
elsif not is_digit(ca) then
return -1;
pragma inline (is_digit, 'yes');
elsif not is_digit(cb) then
return 1;
elsif ca < cb then
if bias = 0 then
bias := -1;
end if;
elsif ca > cb then
if bias = 0 then
bias := 1;
end if;
elsif ca = 0 and cb = 0 then
return bias;
end if;
ia := ia + 1;
ib := ib + 1;
end loop;
end compare_right;
function natcompare(a in varchar2, b in varchar2) return number is
ia number := 0;
ib number := 0;
nza number;
nzb number;
ca char(1 char);
cb char(1 char);
ret number;
begin
loop
-- only count the number of zeroes leading the last number compared
nza := 0;
nzb := 0;
ca := substr(a, ia, 1);
cb := substr(b, ib, 1);
-- skip over leading spaces or zeros
pragma inline (is_whitespace, 'yes');
while is_whitespace( ca ) or ca = '0' loop
if ca = '0' then
nza := nza + 1;
else
-- only count consecutive zeroes
nza := 0;
end if;
ia := ia + 1;
ca := substr(a, ia, 1);
end loop;
pragma inline (is_whitespace, 'yes');
while is_whitespace( cb ) or cb = '0' loop
if cb = '0' then
nzb := nzb + 1;
else
-- only count consecutive zeroes
nzb := 0;
end if;
ib := ib + 1;
cb := substr(b, ib, 1);
end loop;
if ca is null and cb is null then
-- The strings compare the same. Break the tie with the
-- default comparison.
if a < b then
return -1;
elsif a > b then
return 1;
end if;
end if;
-- process run of digits
pragma inline (is_digit, 'yes');
if is_digit(ca) and is_digit(cb) then
ret := compare_right(substr(a, ia), substr(b, ib));
if ret != 0 then
return ret;
end if;
end if;
if ca < cb then
return -1;
elsif ca > cb then
return 1;
end if;
ia := ia + 1;
ib := ib + 1;
end loop;
end natcompare;
begin
if v is null and p_other.v is null then
return 0;
elsif v is null and p_other.v is not null then
return 1;
elsif v is not null and p_other.v is null then
return -1;
elsif v = p_other.v then
return 0;
end if;
return natcompare(v, p_other.v);
end compare;
end;
/
This creates a type in the schema called natural_sort which can be used in SQL and PL/SQL very simply, e.g.:
select * from my_table order by natural_sort(name);This is my test script:
select * from apex_string.split( q'[
fred
pic2
pic100a
pic120
pic121
jane
tom
pic02a
pic3
pic4
1-20
pic100
pic02000
10-20
1-02
1-2
x2-y7
x8-y8
x2-y08
x2-g8
pic01
pic02
pic 6
pic 7
pic 5
pic05
pic 5
pic 5 something
pic 4 else
1.001
1.2
1.002
1.02
1.09
1.101
1.102
1.010
1.10
1.200
1.199
1.198
1.1
2000-1-10
2000-1-2
1999-12-25
2000-3-23
1999-3-3
]' )
order by natural_sort(column_value);The result of the above test query is:
1-02
1-2
1-20
1.001
1.1
1.002
1.02
1.2
1.09
1.010
1.10
1.101
1.102
1.198
1.199
1.200
10-20
1999-3-3
1999-12-25
2000-1-2
2000-1-10
2000-3-23
fred
jane
pic01
pic02
pic02a
pic2
pic3
pic 4 else
pic4
pic 5
pic 5
pic 5 something
pic05
pic 6
pic 7
pic100
pic100a
pic120
pic121
pic02000
tom
x2-g8
x2-y7
x2-y08
x8-y8Warning: this will be slower than the built-in sorting by Oracle, and will not get any benefit from an index on the column; therefore it’s only really suitable when sorting a relatively small number of records, e.g. for display of a small set of records to a user.
About Jeffrey Kemp
Application Designer & Developer at Oracle specialising in Oracle APEX (Application Express), Oracle SQL and PL/SQL. Oracle ACE Alumni ♠️. Piano player, father, husband, Christian. The views expressed on this blog are my own and do not necessarily reflect the views of Oracle.