search

SerenityOS / serenity

The Serenity Operating System 🐞
https://serenityos.org
BSD 2-Clause "Simplified" License
30.69k stars 3.19k forks source link

AK: Stable Sort #12368

Open marcluque opened 2 years ago

marcluque commented 2 years ago

Hey there everybody,

in one of Andreas's more recent videos I saw him sort something with QuickSort while trying to maintain an existing ordering. I thought that maybe switching to a stable sorting algorithm could be beneficial in that case. So I looked into the AK module, but could only find Quicksort. That made me create this issue.

I've been looking into stable sorting algorithms for a bit now and it seems to me that there might be a few candidates. I'd gladly implement whatever is more suited if that would be of interest.

Here are two algorithms that I'd consider suited:

From my understanding TimSort is considered the fastest stable sorting algorithm for "real world data" (e.g., partially sorted data). However, the algorithm has linear worst-case space complexity. That's why I also considered GrailSort which is a stable in-place (i.e., constant worst-case space complexity) sorting algorithm.

I'd be really happy to have a discussion about these algorithms or some other suggestions, as well as my plans to start an implementation.

MaxWipfli commented 2 years ago

It seems that the "TimSort" implementation you referenced is licensed under GNU GPL 2, so this is a no-go, unless the underlying algorithm is widely used by other permissively-licensed projects.

linusg commented 2 years ago

I don't think there's any kind of license or copyright for the underlying algorithm.

marcluque commented 2 years ago

I'm sorry, I should have mentioned that the JDK implementation was supposed to be a reference since I think the documentation header is quite concise and clear. The original idea/specification for the algorithm is described by Tim Peters for Python. I'm not too well versed when it comes to working with licenses, but from my understanding this specification is not licensed? Which should make it possible to use? Please correct me if I'm mistaken.

MaxWipfli commented 2 years ago

The original idea/specification for the algorithm is described by Tim Peters for Python.

Go ahead, then. I wasn't familiar with it and just assumed this was only used by OpenJDK, but then, this seems like a non-issue. Just try to not just port the OpenJDK code, because this would not be allowed by GPL as far as I am aware. I'm looking forward to your PR. :^)

marcluque commented 2 years ago

Very nice, thank you. I think I won't consider the JDK implementation at the moment, since it's quite complex due to the heavy optimizations. I'll get started as soon as possible and also try to adopt the interface that the current Quicksort implementation provides.