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 :slight_smile: 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. [image] GitHub - ZhenyaUsenko/motoko-sort: Fast sorting algorithm implemented in... 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 :slight_smile: 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 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 :slight_smile: Also, being able to index arrays with Nat32 and other numeric types would be very helpful.

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.

Is there a high-level description of the algorithm? Is this similar to radix sort or bucket sort?

It would be fascinating to compare the cycle consumption with typical Rust implementations: the standard slice::sort_unstable,slice::sort, and maybe some version of radix sort that I assume you have implemented.

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!

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.

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?

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))

[image] 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).

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 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)

New Motoko array sorting library

Developers Motoko

skilesare May 30, 2023, 6:40pm 2

Excuse me while I go sort 10 million items like it’s nothing.

coin sorting GIF

Nice @ZhenyaUsenko.

Can it cross over to work with New Vector data structure in Motoko?

Topic		Replies	Views
New Motoko sort package Motoko	3	241	January 11, 2026
Array.sort() is not available when programming Motoko Developers Functional-Programming	7	1044	July 14, 2021
I solved 100 LeetCode Problems using Motoko: Here's what I learned Developers	11	681	August 14, 2024
Completed: ICDevs.org - Bounty 24 - StableBtree Mokoko - up to $10k Bounties & RFPs Discussing	35	4139	October 20, 2023
Motoko Database Developers	13	1756	August 16, 2023

New Motoko array sorting library

Related topics