Merge Sort - Revision history

ObviousAltIsObvious Resident: tag to

2015-01-25T00:18:52Z

← Older revision		Revision as of 17:18, 24 January 2015
Line 7:		Line 7:
	I realize I shouldn't be using iteration in a recursive method... Sue me.		I realize I shouldn't be using iteration in a recursive method... Sue me.

	<~~lsl~~>		<source lang="lsl2">
	list sort(list l) {		list sort(list l) {
	if (llGetListLength(l) > 1) {		if (llGetListLength(l) > 1) {
Line 45:		Line 45:
	return ret;		return ret;
	}		}
	</~~lsl~~>		</source>

Xaviar Czervik: Changed code to be in .

2008-02-08T18:34:38Z

Changed code to be in <lsl>.

← Older revision		Revision as of 11:34, 8 February 2008
Line 7:		Line 7:
	I realize I shouldn't be using iteration in a recursive method... Sue me.		I realize I shouldn't be using iteration in a recursive method... Sue me.

	<~~pre~~>		<lsl>
	list sort(list l) {		list sort(list l) {
	if (llGetListLength(l) > 1) {		if (llGetListLength(l) > 1) {
Line 45:		Line 45:
	return ret;		return ret;
	}		}
	</~~pre~~>		</lsl>

Xaviar Czervik at 17:52, 14 September 2007

2007-09-14T17:52:53Z

← Older revision		Revision as of 10:52, 14 September 2007
Line 5:		Line 5:
	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.		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.

	<pre>		<pre>

Xaviar Czervik: New page: {{LSL Header}} 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 o...

2007-08-26T23:32:53Z

New page: {{LSL Header}} 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 o...

New page

{{LSL Header}}

Created by [[User:Xaviar Czervik|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.

<pre>
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;
}
</pre>

[[Category:LSL Library]]
[[Category:LSL Examples]]