# Merge Sort

 LSL Portal

Created by Xaviar Czervik. Do whatever you wish with this function: Sell it (good luck), use it, or modify it.

This code sorts a list through use of a Merge Sort. I have no idea why you would want to use it as it is more than 150 times slower than llListSort(), but it is a good demonstration of how a Merge Sort works.

I realize I shouldn't be using iteration in a recursive method... Sue me.

```list sort(list l) {
if (llGetListLength(l) > 1) {
integer mid = llGetListLength(l)/2;
list l2 = sort(llList2List(l, 0, mid-1));
list l3 = sort(llList2List(l, mid, -1));
return merge(l2, l3);
}
return l;
}

list merge(list l, list r) {
integer lm = llGetListLength(l);
integer rm = llGetListLength(r);
integer lc;
integer rc;
list ret;
while (lc < lm || rc < rm) {
if (lc >= lm) {
ret += llList2Integer(r, rc);
rc++;
} else if (rc >= rm) {
ret += llList2Integer(l, lc);
lc++;
} else {
if (llList2Integer(l, lc) <= llList2Integer(r, rc)) {
ret += llList2Integer(l, lc);
if (lc < lm)
lc++;
} else {
ret += llList2Integer(r, rc);
if (rc < rm)
rc++;
}
}
}
return ret;
}```