Slightly optimise list:sort

5 files changed, 28 insertions, 6 deletions

diff --git a/CHANGELOG.md b/CHANGELOG.md
index fedd31e..d2d44f6 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -4,6 +4,7 @@
 
 - `list:sort` now requires a compare function as comparison operators now only
   work on Ints.
+- `list:sort`'s performance has been slightly optimised.
 
 ## v0.3.1 - 2019-08-08
 
diff --git a/gen/src/gleam@list.erl b/gen/src/gleam@list.erl
index 411a6c8..7781dcc 100644
--- a/gen/src/gleam@list.erl
+++ b/gen/src/gleam@list.erl
@@ -295,8 +295,7 @@ merge_sort(A, B, Compare) ->
             end
     end.
 
-sort(List, Compare) ->
-    ListLength = length(List),
+do_sort(List, Compare, ListLength) ->
     case ListLength < 2 of
         true ->
             List;
@@ -305,9 +304,16 @@ sort(List, Compare) ->
             SplitLength = ListLength div 2,
             AList = take(List, SplitLength),
             BList = drop(List, SplitLength),
-            merge_sort(sort(AList, Compare), sort(BList, Compare), Compare)
+            merge_sort(
+                do_sort(AList, Compare, SplitLength),
+                do_sort(BList, Compare, ListLength - SplitLength),
+                Compare
+            )
     end.
 
+sort(List, Compare) ->
+    do_sort(List, Compare, length(List)).
+
 range(Start, Stop) ->
     case gleam@int:compare(Start, Stop) of
         eq ->
diff --git a/gen/test/gleam@list_test.erl b/gen/test/gleam@list_test.erl
index 1037884..2411f0b 100644
--- a/gen/test/gleam@list_test.erl
+++ b/gen/test/gleam@list_test.erl
@@ -183,6 +183,10 @@ sort_test() ->
         gleam@list:sort([4, 3, 6, 5, 4], fun gleam@int:compare/2),
         [3, 4, 4, 5, 6]
     ),
+    gleam@expect:equal(
+        gleam@list:sort([4, 3, 6, 5, 4, 1], fun gleam@int:compare/2),
+        [1, 3, 4, 4, 5, 6]
+    ),
     gleam@expect:equal(gleam@list:sort([], fun gleam@int:compare/2), []).
 
 index_map_test() ->
diff --git a/src/gleam/list.gleam b/src/gleam/list.gleam
index ab8b600..24437c6 100644
--- a/src/gleam/list.gleam
+++ b/src/gleam/list.gleam
@@ -244,18 +244,25 @@ fn merge_sort(a, b, compare) {
   }
 }
 
-pub fn sort(list, compare) {
-  let list_length = length(list)
+fn do_sort(list, compare, list_length) {
   case list_length < 2 {
   | True -> list
   | False ->
     let split_length = list_length / 2
     let a_list = take(list, split_length)
     let b_list = drop(list, split_length)
-    merge_sort(sort(a_list, compare), sort(b_list, compare), compare)
+    merge_sort(
+      do_sort(a_list, compare, split_length),
+      do_sort(b_list, compare, list_length - split_length),
+      compare,
+    )
   }
 }
 
+pub fn sort(list, compare) {
+  do_sort(list, compare, length(list))
+}
+
 pub fn range(start, stop) {
   case int:compare(start, stop) {
   | order:Eq -> []
diff --git a/test/gleam/list_test.gleam b/test/gleam/list_test.gleam
index a8b58e0..46e14ea 100644
--- a/test/gleam/list_test.gleam
+++ b/test/gleam/list_test.gleam
@@ -263,6 +263,10 @@ pub fn sort_test() {
   |> list:sort(_, int:compare)
   |> expect:equal(_, [3, 4, 4, 5, 6])
 
+  [4, 3, 6, 5, 4, 1]
+  |> list:sort(_, int:compare)
+  |> expect:equal(_, [1, 3, 4, 4, 5, 6])
+
   // TODO: Requires float:compare
   // [4.1, 3.1, 6.1, 5.1, 4.1]
   // |> list:sort(_, float:compare)