# New Motoko array sorting library **URL:** \ **Category:** Motoko\ **Created:** [May 30, 2023, 5:37pm UTC](https://forum.dfinity.org/t/new-motoko-array-sorting-library/20331 "2023-05-30T17:37:24Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![ZhenyaUsenko](https://sea1.discourse-cdn.com/flex023/user_avatar/forum.dfinity.org/zhenyausenko/32/12200_2.png) [@ZhenyaUsenko](https://forum.dfinity.org/u/ZhenyaUsenko)\ **Post date:** [May 30, 2023, 5:37pm UTC](https://forum.dfinity.org/t/new-motoko-array-sorting-library/20331/1 "2023-05-30T17:37:24Z")
Hi everyone! Today I would like to announce my new library. This time it’s a brand new, in-house built array sorting algorithm implemented in Motoko language. And, as usual, it was made with one simple concept in mind - performance 🙂 Here I need to note that there is a ton-pile of various array sorting methods out there and claiming that something is brand new can be incorrect, as such algorithm as a whole, or partially could be implemented before and we just didn’t know about it. So instead of saying that it is brand new, it would probably be more correct to say that I haven’t seen such one before. > **[GitHub - ZhenyaUsenko/motoko-sort: Fast sorting algorithm implemented in...](https://github.com/ZhenyaUsenko/motoko-sort)** > > Fast sorting algorithm implemented in Motoko language - GitHub - ZhenyaUsenko/motoko-sort: Fast sorting algorithm implemented in Motoko language The version I am releasing today is primarily made for sorting numeric arrays and currently the next types are supported ( **Nat8** , **Nat16** , **Nat32** , **Nat64** , **Int8** , **Int16** , **Int32** , **Int64** ). This, however, doesn’t mean you won’t be able to sort more complex types. An array of **Users** with **name** and **age** properties `User { name: Text; age: Nat32 }` sorted by **age** - no problem. Just pass a property accessor to a sorting function `sort(array, func(user) = user.age)`. More types will come later, including those with non-fixed size (like **Nat** , **Int** , **Text** , **Blob** etc.) so stay tuned 🙂 Those will use an updated version of the algorithm that will be very similar in nature, although having additional complexity and a shift from near-linear performance, unavoidable for types with arbitrary size. Speaking of near-linear performance - yep, that is what my measurements for the algorithm are (you can see them below) - increasing array size by 10 times yields an increase in cycles consumption by roughly 10 times as well. In regards to space complexity, it uses 4 additional arrays to accomplish the goal - 1 twin-array and 3 **Nat32** arrays. The algorithm is stable, so you can subsequently sort your array by different item-properties to achieve the desired behavior that suits your advanced sorting needs. Here is the performance comparison with the existing `Array.sortInPlace` method using arrays of 10 to 10\_000\_000 random **Nat32** items (array size stepping factor is 10). **Cycles cost factor** describes how other array sorting algorithms compare to mine for the same amount of items. **Linearity factor** describes how performance deviates from the previous entry in the table for the same method compared to a perfectly linear algorithm. | Sorting method | Cycles cost | Cycles cost factor | Linearity factor | | --- | --- | --- | --- | | `sortNat32` 10 items | 8\_603 | 1.000 | first entry | | `sortNat32` 100 items | 81\_013 | 1.000 | 0.942 | | `sortNat32` 1\_000 items | 812\_502 | 1.000 | 1.003 | | `sortNat32` 10\_000 items | 8\_189\_344 | 1.000 | 1.008 | | `sortNat32` 100\_000 items | 82\_150\_281 | 1.000 | 1.003 | | `sortNat32` 1\_000\_000 items | 819\_529\_942 | 1.000 | 0.998 | | `sortNat32` 10\_000\_000 items | 8\_193\_990\_495 | 1.000 | 1.000 | | `Array.sortInPlace` 10 items | 21\_563 | 2.506 | first entry | | `Array.sortInPlace` 100 items | 334\_682 | 4.131 | 1.552 | | `Array.sortInPlace` 1\_000 items | 4\_583\_323 | 5.641 | 1.369 | | `Array.sortInPlace` 10\_000 items | 61\_582\_218 | 7.520 | 1.344 | | `Array.sortInPlace` 100\_000 items | 742\_488\_054 | 9.038 | 1.206 | | `Array.sortInPlace` 1\_000\_000 items | 8\_667\_628\_545 | 10.576 | 1.167 | | `Array.sortInPlace` 10\_000\_000 items | hits cycles limit | hits cycles limit | hits cycles limit | Here is the playground where you can check out the library yourself. > **[Motoko Playground - DFINITY](https://m7sm4-2iaaa-aaaab-qabra-cai.ic0.app/?tag=604008378)** > > A playground for the Internet Computer's native Motoko language, brought to you by DFINITY The work on this array sorting library was funded by **ORIGYN Foundation**. **P.S.** I am desperately waiting for those numeric data type conversions to avoid going through **Nat** 🙂 Also, being able to index arrays with **Nat32** and other numeric types would be very helpful. ---
**Author:** ![skilesare](https://sea1.discourse-cdn.com/flex023/user_avatar/forum.dfinity.org/skilesare/32/5609_2.png) [@skilesare](https://forum.dfinity.org/u/skilesare)\ **Post date:** [May 30, 2023, 6:40pm UTC](https://forum.dfinity.org/t/new-motoko-array-sorting-library/20331/2 "2023-05-30T18:40:58Z")
Excuse me while I go sort 10 million items like it’s nothing. ![coin sorting GIF](https://us1.discourse-cdn.com/flex023/uploads/dfn/original/2X/d/ddef8d7d8283a7c997cc00691a6200b70aa3ffba.gif) Nice @ZhenyaUsenko. Can it cross over to work with [New Vector data structure in Motoko](https://forum.dfinity.org/t/new-vector-data-structure-in-motoko/19872)? ---
**Author:** ![ZhenyaUsenko](https://sea1.discourse-cdn.com/flex023/user_avatar/forum.dfinity.org/zhenyausenko/32/12200_2.png) [@ZhenyaUsenko](https://forum.dfinity.org/u/ZhenyaUsenko)\ **Post date:** [May 31, 2023, 7:04am UTC](https://forum.dfinity.org/t/new-motoko-array-sorting-library/20331/3 "2023-05-31T07:04:36Z")
It will be difficult to provide a fully generic interface to support arbitrary array-like structures for sorting (Buffer or Vector you’ve mentioned above, which by the way looks interesting). So for now I think the way to go would be to convert such structures to arrays and sort after. We can consider a better solution later, even creating a separate sorting library for a given data structure if the demand is high would be possible. ---
**Author:** ![timo](https://sea1.discourse-cdn.com/flex023/user_avatar/forum.dfinity.org/timo/32/5543_2.png) [@timo](https://forum.dfinity.org/u/timo)\ **Post date:** [May 31, 2023, 7:38am UTC](https://forum.dfinity.org/t/new-motoko-array-sorting-library/20331/4 "2023-05-31T07:38:45Z")
Is there a high-level description of the algorithm? Is this similar to radix sort or bucket sort? ---
**Author:** ![roman-kashitsyn](https://sea1.discourse-cdn.com/flex023/user_avatar/forum.dfinity.org/roman-kashitsyn/32/3802_2.png) [@roman-kashitsyn](https://forum.dfinity.org/u/roman-kashitsyn)\ **Post date:** [May 31, 2023, 7:45am UTC](https://forum.dfinity.org/t/new-motoko-array-sorting-library/20331/5 "2023-05-31T07:45:05Z")
It would be fascinating to compare the cycle consumption with typical Rust implementations: the standard [slice::sort\_unstable](https://doc.rust-lang.org/nightly/std/primitive.slice.html#method.sort_unstable),[slice::sort](https://doc.rust-lang.org/nightly/std/primitive.slice.html#method.sort), and maybe some version of [radix sort](https://crates.io/crates/radsort) that I assume you have implemented. ---
**Author:** ![nomeata](https://sea1.discourse-cdn.com/flex023/user_avatar/forum.dfinity.org/nomeata/32/733_2.png) [@nomeata](https://forum.dfinity.org/u/nomeata)\ **Post date:** [May 31, 2023, 8:20am UTC](https://forum.dfinity.org/t/new-motoko-array-sorting-library/20331/6 "2023-05-31T08:20:54Z")
Since this is better™ than the one in base, can it simply be made the algorithm provided by base? Ah, it’s specialized to the element type, so not a drop-in replacement? Ok, then probably better as a separate library. Thanks, great work! ---
**Author:** ![ZhenyaUsenko](https://sea1.discourse-cdn.com/flex023/user_avatar/forum.dfinity.org/zhenyausenko/32/12200_2.png) [@ZhenyaUsenko](https://forum.dfinity.org/u/ZhenyaUsenko)\ **Post date:** [May 31, 2023, 8:57am UTC](https://forum.dfinity.org/t/new-motoko-array-sorting-library/20331/7 "2023-05-31T08:57:51Z")
I’ll work on the algorithm description soon, maybe even capture a video-description. It has some similarities with MSD radix sort, doesn’t use lexicographic sorting though. ---
**Author:** ![rossberg](https://sea1.discourse-cdn.com/flex023/user_avatar/forum.dfinity.org/rossberg/32/795_2.png) [@rossberg](https://forum.dfinity.org/u/rossberg)\ **Post date:** [May 31, 2023, 9:22am UTC](https://forum.dfinity.org/t/new-motoko-array-sorting-library/20331/8 "2023-05-31T09:22:25Z")
I’d be very curious to know how much of the win over the base library is due to being type-specialised and hence avoiding the overhead of calling a comparison function, and how much is due to algorithmic factors. If you turned yours into a generic version, what would the numbers be? ---
**Author:** ![ZhenyaUsenko](https://sea1.discourse-cdn.com/flex023/user_avatar/forum.dfinity.org/zhenyausenko/32/12200_2.png) [@ZhenyaUsenko](https://forum.dfinity.org/u/ZhenyaUsenko)\ **Post date:** [May 31, 2023, 9:38am UTC](https://forum.dfinity.org/t/new-motoko-array-sorting-library/20331/9 "2023-05-31T09:38:28Z")
All of the currently supported types ( **Nat8** , **Nat16** , **Nat32** , **Nat64** , **Int8** , **Int16** , **Int32** , **Int64** ) use practically the same algorithm, just do different type conversions under the hood. Current algorithm can not be turned into fully generic. You won’t be able to sort text with it. As I mentioned before, the version of the algorithm that works with non-fixed size data types is also planned. You can potentially sort **Int** and **Nat** with the current implementation, but I am not satisfied with the performance. I will be able to achieve noticeably better results for **Int** and **Nat** with the updated (additional) version that will specialize on sorting non-fixed size data types. If you can tolerate truncating your **Nat** / **Int** to 64bits, it is easy to sort them now `sortNat64(array, func(nat) = natToNat64(nat))` ---
**Author:** ![timo](https://sea1.discourse-cdn.com/flex023/user_avatar/forum.dfinity.org/timo/32/5543_2.png) [@timo](https://forum.dfinity.org/u/timo)\ **Post date:** [May 31, 2023, 12:26pm UTC](https://forum.dfinity.org/t/new-motoko-array-sorting-library/20331/10 "2023-05-31T12:26:06Z")
> [@rossberg](#): > > I’d be very curious to know how much of the win over the base library is due to being type-specialised and hence avoiding the overhead of calling a comparison function, and how much is due to algorithmic factors. If you turned yours into a generic version, what would the numbers be? On purely theoretical grounds, the algorithm cannot be based on a comparison function because the achieved complexity is O(n). ---
**Author:** ![ZhenyaUsenko](https://sea1.discourse-cdn.com/flex023/user_avatar/forum.dfinity.org/zhenyausenko/32/12200_2.png) [@ZhenyaUsenko](https://forum.dfinity.org/u/ZhenyaUsenko)\ **Post date:** [June 1, 2023, 6:03pm UTC](https://forum.dfinity.org/t/new-motoko-array-sorting-library/20331/11 "2023-06-01T18:03:20Z")
I’ve made a video description of the algorithm. Sorry for it being so clunky and long, I don’t have much experience in video capturing. You can watch it at 1.5x speed if you want. > **[Sort algorithm description.mp4](https://drive.google.com/file/d/1yaqyww1KEanstufRmaHCT1sR8PIIn4jp/view?usp=sharing)** > > Google Drive file. (seems like 1080p doesn’t want to show up in the player, you can download the file to watch it in the original resolution) ---
**Author:** ![ZhenyaUsenko](https://sea1.discourse-cdn.com/flex023/user_avatar/forum.dfinity.org/zhenyausenko/32/12200_2.png) [@ZhenyaUsenko](https://forum.dfinity.org/u/ZhenyaUsenko)\ **Post date:** [June 1, 2023, 7:26pm UTC](https://forum.dfinity.org/t/new-motoko-array-sorting-library/20331/12 "2023-06-01T19:26:41Z")
> [@roman-kashitsyn](#): > > It would be fascinating to compare the cycle consumption with typical Rust implementations: the standard [slice::sort\_unstable](https://doc.rust-lang.org/nightly/std/primitive.slice.html#method.sort_unstable),[slice::sort](https://doc.rust-lang.org/nightly/std/primitive.slice.html#method.sort), and maybe some version of [radix sort](https://crates.io/crates/radsort) that I assume you have implemented. I don’t have much experience with Rust development. I will do this comparison eventually but it may take a while… Maybe there are some volunteers?) ---
**Author:** ![ZhenyaUsenko](https://sea1.discourse-cdn.com/flex023/user_avatar/forum.dfinity.org/zhenyausenko/32/12200_2.png) [@ZhenyaUsenko](https://forum.dfinity.org/u/ZhenyaUsenko)\ **Post date:** [June 4, 2023, 11:12am UTC](https://forum.dfinity.org/t/new-motoko-array-sorting-library/20331/13 "2023-06-04T11:12:53Z")
Here is a simple description of the algorithm for those who don’t want to watch the video 1. initialize the sorting _range_ to **[0, length - 1]** 2. iterate through the _range_ and find **min** and **max** values - fast return if no cases with **(prev value \> value)** found 3. set all items from the _range_ in the **counts** array to **0** 4. for each **item** from the _range_ in the input array - calculate a new **index** as `rangeFrom + (item - min) / ((max - min) / (rangeTo - rangeFrom))` - increment **counts** array at this **index** 5. initialize **totalCount** to _rangeFrom_ 6. for each **count** from the _range_ in the **counts** array which is not **0** - set **shifterCounts** array at index **totalCount** to **count** - replace **count** in the **counts** array with **totalCount** - add **count** to **totalCount** 7. for each **item** from the _range_ in the input array - calculate a new **index** as `rangeFrom + (item - min) / ((max - min) / (rangeTo - rangeFrom))` - get **count** from **counts** array at this **index** - set **twinArray** at index **count** to current **item** - increment **counts** array at **index** 8. update all items from the _range_ in the input array with values from **twinArray** 9. for each **index** and **count** from the _range_ in the **shifterCounts** array where **count** is greater than **1** run steps **2-9** with the _range_ set to **[index, index + count - 1]** ---
**Author:** ![rossberg](https://sea1.discourse-cdn.com/flex023/user_avatar/forum.dfinity.org/rossberg/32/795_2.png) [@rossberg](https://forum.dfinity.org/u/rossberg)\ **Post date:** [June 4, 2023, 2:24pm UTC](https://forum.dfinity.org/t/new-motoko-array-sorting-library/20331/14 "2023-06-04T14:24:29Z")
@ZhenyaUsenko, thanks for the summary. So this is an example of trading time complexity for space complexity, since this algorithm appears to take O(n) extra space, whereas traditional in-place sorting algorithms are O(1) (or O(log N) if you count stack space). Given that Motoko is a GC-ed language, an accurate measurement of time complexity would probably have to account for the extra GC time this induces, but in the end that should still only amount to constant factors. ---
**Author:** ![ZhenyaUsenko](https://sea1.discourse-cdn.com/flex023/user_avatar/forum.dfinity.org/zhenyausenko/32/12200_2.png) [@ZhenyaUsenko](https://forum.dfinity.org/u/ZhenyaUsenko)\ **Post date:** [June 4, 2023, 3:05pm UTC](https://forum.dfinity.org/t/new-motoko-array-sorting-library/20331/15 "2023-06-04T15:05:01Z")
In terms of space complexity, this algorithm takes 12 bytes of additional space for each item to be exact. In my measurements `Array.sortInPlace` takes 4 bytes of additional space for each item, which is not O(1). In both cases, when sorting arrays of complex structures, which should be a more common real world usage than just arrays of plain numbers, this extra space, in my opinion, can be regarded as negligible. ---
**Author:** ![rossberg](https://sea1.discourse-cdn.com/flex023/user_avatar/forum.dfinity.org/rossberg/32/795_2.png) [@rossberg](https://forum.dfinity.org/u/rossberg)\ **Post date:** [June 4, 2023, 5:10pm UTC](https://forum.dfinity.org/t/new-motoko-array-sorting-library/20331/16 "2023-06-04T17:10:14Z")
Oh, indeed, sortInPlace uses a scratch array of size N. I don’t know why that particular algorithm was chosen. ---
**Author:** ![timo](https://sea1.discourse-cdn.com/flex023/user_avatar/forum.dfinity.org/timo/32/5543_2.png) [@timo](https://forum.dfinity.org/u/timo)\ **Post date:** [June 4, 2023, 8:07pm UTC](https://forum.dfinity.org/t/new-motoko-array-sorting-library/20331/17 "2023-06-04T20:07:43Z")
> [@rossberg](#): > > Given that Motoko is a GC-ed language, an accurate measurement of time complexity would probably have to account for the extra GC time this induces, but in the end that should still only amount to constant factors. If the algorithm produces O(n) garbage but completes in one message, before GC runs, then doesn’t that add no GC time at all? I mean because GC time is a function of the live heap not the garbage. ---
**Author:** ![rossberg](https://sea1.discourse-cdn.com/flex023/user_avatar/forum.dfinity.org/rossberg/32/795_2.png) [@rossberg](https://forum.dfinity.org/u/rossberg)\ **Post date:** [June 5, 2023, 4:17pm UTC](https://forum.dfinity.org/t/new-motoko-array-sorting-library/20331/18 "2023-06-05T16:17:32Z")
@timo, that depends on the GC strategy. E.g., with Motoko’s incremental GC, the trade-off may shift somewhat (others would know better than I). In general, short-lived garbage should indeed be cheap, but not entirely free. For starters, creating a lot of garbage causes the GC to run more often. ---
**Author:** ![ZhenyaUsenko](https://sea1.discourse-cdn.com/flex023/user_avatar/forum.dfinity.org/zhenyausenko/32/12200_2.png) [@ZhenyaUsenko](https://forum.dfinity.org/u/ZhenyaUsenko)\ **Post date:** [August 22, 2023, 11:41am UTC](https://forum.dfinity.org/t/new-motoko-array-sorting-library/20331/19 "2023-08-22T11:41:18Z")
Just released a new minor version with further performance optimizations. On average, it has 28% better performance than the previous version. The updated version utilizes the newly added adjacent numeric type conversions. They contribute to the performance improvements a little bit. The main advantage though is the ability to remove a hack I used for **sortNat32** to avoid going through Bigint and just use **nat32toNat64** instead. Thanks @kentosugama for that. > **[GitHub - ZhenyaUsenko/motoko-sort: Fast sorting algorithm implemented in...](https://github.com/ZhenyaUsenko/motoko-sort)** > > Fast sorting algorithm implemented in Motoko language - GitHub - ZhenyaUsenko/motoko-sort: Fast sorting algorithm implemented in Motoko language Here is the updated performance comparison table. | Sorting method | Cycle cost | Cycle cost factor | Linearity factor | | --- | --- | --- | --- | | sortNat32 10 items | 5\_574 | 1.000 | first entry | | sortNat32 100 items | 51\_852 | 1.000 | 0.930 | | sortNat32 1\_000 items | 518\_850 | 1.000 | 1.000 | | sortNat32 10\_000 items | 5\_241\_389 | 1.000 | 1.010 | | sortNat32 100\_000 items | 52\_557\_449 | 1.000 | 1.003 | | sortNat32 1\_000\_000 items | 524\_319\_238 | 1.000 | 0.998 | | sortNat32 10\_000\_000 items | 5\_244\_394\_674 | 1.000 | 1.000 | | Array.sortInPlace 10 items | 19\_684 | 3.531 | first entry | | Array.sortInPlace 100 items | 302\_719 | 5.838 | 1.538 | | Array.sortInPlace 1\_000 items | 4\_128\_550 | 7.957 | 1.364 | | Array.sortInPlace 10\_000 items | 55\_342\_852 | 10.559 | 1.340 | | Array.sortInPlace 100\_000 items | 666\_151\_264 | 12.675 | 1.204 | | Array.sortInPlace 1\_000\_000 items | 7\_768\_693\_694 | 14.817 | 1.166 | | Array.sortInPlace 10\_000\_000 items | hits cycle limit | hits cycle limit | hits cycle limit | I am going to replace the table in the original post soon. ---
**Author:** ![ZhenyaUsenko](https://sea1.discourse-cdn.com/flex023/user_avatar/forum.dfinity.org/zhenyausenko/32/12200_2.png) [@ZhenyaUsenko](https://forum.dfinity.org/u/ZhenyaUsenko)\ **Post date:** [December 6, 2025, 6:04pm UTC](https://forum.dfinity.org/t/new-motoko-array-sorting-library/20331/20 "2025-12-06T18:04:42Z")
A new patch was just released fixing a bug that was preventing the algorithm from being stable. The algorithm was designed as stable (and it was at first), but in one of the latest versions I broke the stability when I added fast paths for sorting `2/3/4-item` array parts. It utilizes [sorting networks](https://en.wikipedia.org/wiki/Sorting_network) for those `2/3/4-item` parts instead of running the full algorithm. However `4-item` sorting function wasn’t stable preventing the whole algorithm from being stable as well. The bug was recently spotted by @timo ( [Algorithm isn't stable · Issue #1 · ZhenyaUsenko/motoko-sort · GitHub](https://github.com/ZhenyaUsenko/motoko-sort/issues/1) ) and was fixed in the latest version [v0.6.1](https://github.com/ZhenyaUsenko/motoko-sort)