The dual quicksort provides a way to sort two lists in order to preserve the mapping between the two.

# Summary This is an implementation of Quicksort. Since LSL deals mostly with lists, it is a nice platform to discuss divide-and-conquer sorting algorithms. The following are two different implementations: one for sorting integers and the other for sorting strings. The procedure is pretty much the same and the Quicksort function itself uses a comparer function which does the actual comparison between two elements of the same type. I have implemented it this way to show that one can work generically without having to necessarily adapt the Quicksort algorithm to every single case of the sorted type.

# Code

quicksort_integers.lsl
```// Gremlin: See Quicksort Integers, Quicksort Strings and Quicksort Map Stable
list sortIntegers = [ 3,7,8,5,2,1,9,5,4 ];

integer integerComparer(list a, list b) {
if(llList2Integer(a, 0) <= llList2Integer(b, 0)) return TRUE;
return FALSE;
}

list quicksort(list a) {

if(llGetListLength(a) <= 1) return a;

list pivot = llList2List(a, llGetListLength(a)/2, llGetListLength(a)/2);
a = llDeleteSubList(a, llGetListLength(a)/2, llGetListLength(a)/2);

list less = [];
list more = [];

integer i;
for(i=0; i<llGetListLength(a); i++) {
if(integerComparer(llList2List(a, i, i), pivot) == TRUE)
less += llList2List(a, i, i);
else
more += llList2List(a, i, i);
}
return quicksort(less) + (list)pivot + quicksort(more);

}

default
{
state_entry()
{
llOwnerSay("Sorted list contains in order: " + llDumpList2String(quicksort(sortIntegers), " "));
}
}```

And for strings, the sort criteria is the lexicographical order of lowercase letters. You can easily change the alphabet by modifying the list `alph`, declared and initialized within the `stringComparer` function. For example, you could use this to add your own sorting criteria. The relative order of elements is what makes the `stringComparer` function work.

quicksort_strings.lsl
```// Gremlin: See Quicksort Integers, Quicksort Strings and Quicksort Map Stable
list sortStrings = [ "aza", "aba", "aaa", "ana", "ban", "aaaa", "abarbecue" ];

integer stringComparer(list a, list b) {

list alph = [ "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z" ];

integer i;

for(i=0; i<llStringLength(llList2String(a, 0)) && i<llStringLength(llList2String(b, 0)); i++) {
if(llListFindList(alph, (list)llGetSubString(llList2String(a, 0), i, i)) < llListFindList(alph, (list)llGetSubString(llList2String(b, 0), i, i))) {
return TRUE;
}
if(llListFindList(alph, (list)llGetSubString(llList2String(a, 0), i, i)) > llListFindList(alph, (list)llGetSubString(llList2String(b, 0), i, i))) {
return FALSE;
}

}
return TRUE;
}

list quicksort(list a) {

if(llGetListLength(a) <= 1) return a;

list pivot = llList2List(a, llGetListLength(a)/2, llGetListLength(a)/2);
a = llDeleteSubList(a, llGetListLength(a)/2, llGetListLength(a)/2);

list less = [];
list more = [];

integer i;
for(i=0; i<llGetListLength(a); i++) {
if(stringComparer(llList2List(a, i, i), pivot) == TRUE)
less += llList2List(a, i, i);
else
more += llList2List(a, i, i);
}
return quicksort(less) + (list)pivot + quicksort(more);

}

default
{
state_entry()
{
llOwnerSay("Sorted list contains in order: " + llDumpList2String(quicksort(sortStrings), " "));
}
}```

As you can see between both versions, the `quicksort` function makes use of lists being containers in order to work with data without type-casting to their corresponding types and thus changes only the comparer: `integerComparer` or `stringComparer` between the two versions given above. This allows you to create your own comparer function as plugins to Quicksort. 