[m-rev.] diff: improve efficiency of list__merge_sort

[Simon Taylor]

Estimated hours taken: 0.25
Branches: main

library/list.m:
	Improve efficiency of list__merge_sort by not recomputing
	the length of the list at each step.

Index: list.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/list.m,v
retrieving revision 1.99
diff -u -u -r1.99 list.m
--- list.m	2001/05/31 06:00:04	1.99
+++ list.m	2001/08/14 07:25:11
@@ -930,18 +930,26 @@
 :- mode list__merge_sort(in, out) is det.
 :- pragma type_spec(list__merge_sort(in, out), T = var(_)).
 
-list__merge_sort([], []).
-list__merge_sort([X], [X]).
 list__merge_sort(List, SortedList) :-
-	List = [_,_|_],
-	list__length(List, Length),
-	HalfLength is Length // 2,
-	( list__split_list(HalfLength, List, Front, Back) ->
-		list__merge_sort(Front, SortedFront),
-		list__merge_sort(Back, SortedBack),
-		list__merge(SortedFront, SortedBack, SortedList)
+	list__merge_sort_2(list__length(List), List, SortedList).
+
+:- pred list__merge_sort_2(int, list(T), list(T)).
+:- mode list__merge_sort_2(in, in, out) is det.
+:- pragma type_spec(list__merge_sort_2(in, in, out), T = var(_)).
+
+list__merge_sort_2(Length, List, SortedList) :-
+	( Length > 1 ->
+		HalfLength = Length // 2,
+		( list__split_list(HalfLength, List, Front, Back) ->
+			list__merge_sort_2(HalfLength, Front, SortedFront),
+			list__merge_sort_2(Length - HalfLength,
+				Back, SortedBack),
+			list__merge(SortedFront, SortedBack, SortedList)
+		;
+			error("list__merge_sort_2")
+		)
 	;
-		error("list__merge_sort")
+		SortedList = List
 	).
 
 %-----------------------------------------------------------------------------%
--------------------------------------------------------------------------
mercury-reviews mailing list
post:  mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------