Sorting algorithms that don’t hate you
medium.com
medium.com
It is a new stable sorting algorithm that is a hybrid of quicksort and mergesort which is much faster for random data, while still taking full advantage of pre-existing order or inputs with many duplicates. On an Apple M1 in Rust the latest version is ~4.5x faster than the stdlib slice::sort for sorting 2^25 random integers while using 4 times less extra memory. It is 11.5x faster if you happen to sort only 4096 distinct integers with many duplicates. Note that the algorithm is purely comparison based and does not contain special type-dependent SIMD stuff.
I have a short preliminary talk on glidesort here: https://www.youtube.com/watch?v=2y3IK1l6PI4.
Perhaps the V8 people will be interested in it as well.
Is Glidesort1024 still stable?
I thought that sorting algorithms were at a culminating point, but it appears this is not the case at all.
(Here's where I hope I'm asking a dumb question and you already have, but I haven't been able to find it.)
I would assume that they're faster, especially if using SIMD.
Timsort is from 2002. Not sure where this comes from. Perhaps it wasn't as popular or widely known in 2008 as it is now, but I actually learned about it at about that time. See also:
https://mail.python.org/pipermail/python-dev/2002-July/02683...
(edit: timsort was introduced to Java in 2009, per https://bugs.openjdk.org/browse/JDK-6804124, and knowledge of it would probably have spread much further from that point, so maybe that's the source of confusion?)
Like it probably doesn't matter if you're sorting 10k entries, but when you're sorting several gigabytes it really does.
The actual implementation in Toit does depth first, so eg. the leftmost 8,8->16 merge is done as soon as the 8-element ranges are ready.
Collecting those nine elements looks terrible for locality.
Funnelsort is a cache oblivious variant of merge sort which is provably cache optimal in some sense. I haven't tried implementing it.
https://en.wikipedia.org/wiki/Introsort#Implementations
And heapsort has terrible cache behaviour.
Eventually I realized I was running out of desk space, so I started merging little stacks of around equal size.
So the base case wasn’t 1 element, but that’s conventional for actual implementations. And the splitting wasn’t quite recursive I guess. But partial credit at least.
This cost model is an important reason to merge bottom up, from sorted subsequences, without arbitrary splitting that can add work but not reduce it.
I think back on it with a certain amount of nostalgia now, but it was a stupid way to do operations, even at the time, They had invested big in computers in the 70's and were still maintaining the same tech stack in the early 00's when I worked there.
(With that said, Timsort must be faster in practice than this kind of retrofitted unstable sort. I’m curious how large the difference is.)
But yeah, I don't usually need stability either.
Let's say you're sorting a bunch a unlabelled images. You can sort them by number of pixels, that's pretty clear but will likely have clashes.
You could then sort by either width of height next, but the choice is pretty arbitrary. It's not obvious why a 100x10 pixel image should come before or after a 10x100 pixel image. But it's not very weird to pick one either.
Next you could sort on properties of the first pixel. But those are multidimensional. Sorting by the most red first, for example, would be weird.
You could still create an ordering if you need the consistency, but it wouldn't mean anything.
If you don't sort by them, you can get images that are different in ways that aren't sorted. Stability (well, instability) becomes detectable.
If you have to use an unstable sorting algorithm you'll be stuck choosing between images jumping around or being in a certain spot because the 34th pixel on the 56th line is slightly more greenish than in the image before it. It can depend on your use case which of those is least desirable.
Having a stable sort would give you another option.
Asking because you're actually describing a problem I have with a data set :D
The easiest way to transform an unstable sort into a stable sort is probably mapping input from T -> (Index, T) and including the index as a sort key.
I vaguely recall JSC actually having a literal tree sort at one point to deal with this.
This is in a JS engine, where by design all code is untrusted.
If you are a JS engine, then arbitrary code execution, failure to terminate, or crashing is never an acceptable outcome, regardless of how bad the code is, because again, you're dealing with untrusted input. The assumption for a JS engine is necessarily that all code is malicious.
But the JS engine does not protect against the page containing JS code that loops forever. How would it even do that?
Edit: Perhaps some misunderstanding: V8 "just used Quicksort", but it never used the qsort function from the C library. That would not have worked with garbage collection, since you can have a garbage collection in the middle of sorting, which could move the array.
But the point is that the general quicksort algorithm does a bunch of unsafe memory accesses if the comparator is unstable (either directly or by modification of the sorted data). As demonstrated by every qsort implementation going wrong in unsafe ways in such a scenario.
Now maybe you used a version of qsort that actually made sure it wasn’t going out of bounds and what not and did … something? When that occurred, and saying what that something was would be a reasonable answer.
As for qsort() not being an option due to gc, that’s only a problem due to v8’s gc - JSC for instance could just use qsort or what not if it was sure the sort was consistent.
Not the prettiest code, but it's in the examples directory at https://github.com/toitware/toit-png-display if anyone cares.
> Toit is a modern high-level language designed specifically for microcontrollers
> Toit is optimised for live reloading on your microcontroller. Your code runs incrementally as you write it and you get instant feedback. Push changes over your local WiFi in two seconds and reserve your USB cable for charging your phone. You iterate quickly, learn fast, and build better things.
Most can be done in place with some effort.
Then you need to worry not about asymptotics, but the constant factors. Quicksort has significantly lower operation count than heap sort, even though both are O(nlog n). For small numbers bubble sort is quicker than both (and many good sorts leverage this via hybrid methods). Caches add another massive game changing performance dial to fiddle with.
Taking stock at this level, ignoring that many of the non-green field he chose can be made green, misses important nuance.
A number n is bit reversed if it is written was written in binary (base 2) and then the bits were written in reverse order.
Last time I looked at Shell sort, when sorting n records on keys in bit reversed order, the iterations of Shell sort did nothing until the last iteration at which time Shell sort was just bubble sort or some such and, whatever, ran in time O(n^2) where the O() is some obscure but now common notation. The article claims something smaller than O(n^2). Okay, but to get something smaller, have to tweak what used to be a standard version of Shell sort.
For another point, the article wants a stable sort -- if two records (the data being sorted) A and B have equal keys and before the sort record A is before record B, then after the sort record A will still be before record B. But, if want a stable sort, then for one approach, before the sort, number the records and use these numbers as part of the keys. Right this extra step runs in time O(n) and uses extra temporary, working storage proportional to n. For current computing, is this extra storage a meaningful issue?
My favorite is heap sort, guaranteed O(n log(n)) average case and worst case, meets the Gleason bound and, thus, is the fastest possible sort based on comparing pairs of keys (in one of volumes of D. Knuth, The Art of Computer Programming).
You mentioned simple: The logic of the heap data structure and its corresponding code seem to be relatively simple.
Of course, radix sort does not work by "comparing pairs of keys", may be regarded as O(n), and, check this, may also be stable. Of course, radix sort was the algorithm of the IBM punched card sorting machine so maybe goes back to before 1900 and, thus, is likely the oldest of the common sorting algorithms.
Below (in a separate post) is code for
ai_heap_sort02
Right, this code is for only ascending, integers, and arrays and, thus, is far from the practice of generic code, e.g., as in
https://en.wikipedia.org/wiki/Generic_programming
The advantages of generic code my work doesn't really need. Once I wrote some generic code, and that experience was enough!
The code is in Microsoft's Visual Basic .NET.
Why Visual Basic .NET?
I have written some C code. There are claims that the programming language C has idiosyncratic syntax. Whatever it has, I don't like its syntax. I.e., supposedly
i = ++j+++++k++
i = ++j+++++k++
Maybe C and C++ are essential for Windows internals and for Windows applications that make direct use of the System32 API, but I've never written such code since my background is applied math software.
Thus, also I don't like the related syntax of C++ or C#.
The syntax of Visual Basic .NET (VB) is more traditional, more like the original Basic, then Fortran, Algol, Pascal, and PL/I (maybe my favorite).
Thus, VB is relatively easy to teach, learn, read, and write, and these attributes might be considered important in a large project!
Whatever the syntax of VB is, there are claims that VB and C# have equivalent semantics and differ only in syntactic sugar. I.e., supposedly there is a source code translator program than can translate code in either of VB or C# to the other.
So, for my project, code to run on Windows, I am writing in VB instead of C#.
Also below (in a separate post) is code
Function obj_heap_insert
Here I use the heap data structure, the main idea in heap sort, to maintain a priority queue. So, with this code can look at 20 million objects one at a time and end up with, e.g., the 20 largest. Uh, how else to do that???!!!
Right, this code starts to be a little big generic.
Right, operating on the heap data structure can hurt possibly desired main memory and cache memory locality of reference, but there is at least one modification of modifying operations on a heap that speed up what otherwise might be the case of a heap large enough to need virtual memory.
All this code appears to run correctly. I have later versions modified, longer, less easy to read, to use an error handling technique I cooked up -- really simple, I wouldn't recommend for large projects and it will likely become a case of technical debt if my work grows a lot!
Uh, my view, a judgment call, is that the article and my post here go deeper into sorting than we should. I want to declare sorting as a plenty well enough understood, solved problem and move on to other challenges.
' Ascending integer (Int32) heap sort.
'
' For i = 1, 2, ..., n, sort components of key_array(i)
' into ascending order using heap sort.
'
' We check parameters for reasonable values and, in case of
' a error, raise the error condition.
'
' Upon return, for i = 1, 2, ..., n - 1,
'
' key_array( i ) <= key_array( i + 1 )
'
' The code here is 'structured' in the sense of E. Dijkstra
' and, thus, is without the GOTO statements of own Watson
' PL/I heap sort code.
'
' The array subscript logic here is done carefully enough
' that it should never overflow even for the largest
' possible value of n.
'
' For some constant k (depending on the computer, compiler,
' etc. but not depending on the parameters) the execution
' time is guaranteed to be closely just
'
' k*n*log(n)
'
' in the worst case.
'
' The code here needs a 'sift' loop in two places; the code
' is the same in both places.
'
' The work here is 'in place', that is, uses no storage
' whose size depends on the passed parameters.
'
Sub ai_heap_sort02( _
ByRef key_array() As Int32, _
ByVal n As Int32 )
Dim routine_name As String = "ai_heap_sort02"
Dim error_code As Int32 = 0
Dim i_2 As Int32 = 2
Dim i_first, i_middle, i_last As Int32
Dim i_father0 As Int32
Dim i_father, i_child1, i_child2, i_max_child As Int32
' We need one working location of data type the same as the
' components of parameter key_array():
Dim key_father As Int32
Try
' Get started:
error_code = 1001
If n <= 0 Then err.raise(error_code, routine_name)
error_code = 1002
If key_array.GetUpperBound(0) < n Then
err.raise(error_code, routine_name)
End If
error_code = 1003
i_first = 1
i_last = n
i_middle = i_last \ i_2
i_father0 = i_middle + 1
' Build heap
Do
i_father0 = i_father0 - 1
If i_father0 < i_first Then Exit Do
key_father = key_array( i_father0 )
i_father = i_father0
' Sift
Do
If i_father < i_middle Then
i_child1 = i_father + i_father
i_child2 = i_child1 + 1
If key_array( i_child1 ) > key_array( i_child2 ) Then
i_max_child = i_child1
Else
i_max_child = i_child2
End If
If key_array( i_max_child ) > key_father Then
key_array( i_father ) = key_array( i_max_child )
i_father = i_max_child
Continue Do
Else
key_array( i_father ) = key_father
Exit Do
End If
Else ' i_father >= i_middle
If i_father > i_middle Then
key_array( i_father ) = key_father
Exit Do
End If
i_child1 = i_father + i_father ' i_father = i_middle
If i_child1 < i_last Then
i_child2 = i_child1 + 1
If key_array( i_child1 ) > key_array( i_child2 ) Then
i_max_child = i_child1
Else
i_max_child = i_child2
End If
Else ' i_child1 = i_last
i_max_child = i_child1
End If
If key_array( i_max_child ) > key_father Then
key_array( i_father ) = key_array( i_max_child )
key_array ( i_max_child ) = key_father
Else
key_array ( i_father ) = key_father
End If
Exit Do
End If
Loop ' End of sift loop
Loop ' End of build heap loop
' Sort heap
i_first = 1
i_last = n
Do
key_father = key_array( i_last )
key_array( i_last ) = key_array( i_first )
key_array( i_first ) = key_father
i_father = i_first
i_last = i_last - 1
If i_last <= i_first Then Exit Do
i_middle = i_last \ 2
' Sift
Do
If i_father < i_middle Then
i_child1 = i_father + i_father
i_child2 = i_child1 + 1
If key_array( i_child1 ) > key_array( i_child2 ) Then
i_max_child = i_child1
Else
i_max_child = i_child2
End If
If key_array( i_max_child ) > key_father Then
key_array( i_father ) = key_array( i_max_child )
i_father = i_max_child
Continue Do
Else
key_array( i_father ) = key_father
Exit Do
End If
Else ' i_father >= i_middle
If i_father > i_middle Then
key_array( i_father ) = key_father
Exit Do
End If
i_child1 = i_father + i_father ' i_father = i_middle
If i_child1 < i_last Then
i_child2 = i_child1 + 1
If key_array( i_child1 ) > key_array( i_child2 ) Then
i_max_child = i_child1
Else
i_max_child = i_child2
End If
Else ' i_child1 = i_last
i_max_child = i_child1
End If
If key_array( i_max_child ) > key_father Then
key_array( i_father ) = key_array( i_max_child )
key_array ( i_max_child ) = key_father
Else
key_array ( i_father ) = key_father
End If
Exit Do
End If
Loop ' End of sift loop
Loop ' End of sort heap loop
Catch
err.raise(error_code, routine_name)
End Try
out:
Return
End Sub static <T>void shellSort(T[] a, Comparator<T> c) {
int n = a.length;
int h = 16, g = 1;
while (n > g) {
h = h + h + h / 4 + 16;
g = (h + 15) / 16;
}
do {
h = (h - 16) * 4 / 9;
g = (h + 15) / 16;
for (int i = g; i < n; i++) {
T t = a[i];
int j = i;
for (; j >= g && c.compare(a[j - g], t) > 0; j -= g) {
a[j] = a[j - g];
}
a[j] = t;
}
} while (g > 1);
}
' Function obj_heap_insert
' Object heap insert to use the heap algorithm to maintain
' a 'priority queue'.
'
' So, suppose for positive integer n we have x(i) for i =
' 1, 2, ..., n and for positive integer m <= n we want the
' m largest of the x(i). So, we allocate an array y(j), j
' = 1, 2, ..., m.
'
' Suppose we regard y as an ascending heap, e.g., so that
' y(1) <= y(j), j = 2, ..., k <= m where the number of
' locations of y in use so far is integer k where 0 <= k <=
' m.
'
' Then for i = 1, 2, ..., n, we consider inserting x(i)
' into the heap.
'
' If k < m, then we set k = k + 1 and set y(k) = x(i) and
' 'sift' to 'promote' the value in y(k) until we have a
' heap again.
'
' If k = m, then we compare x(i) and y(1). If x(i) <= y(1),
' then we are done with x(i). Else, x(i) > y(1) and y(1) is
' not among the m largest and, to 'remove' value y(1) we
' set y(1) = x(i) and 'sift' the value in y(1) to create a
' heap again.
'
' After i = n, y contains the m largest of x(i), i = 1, 2,
' ..., n.
'
' The advantage of this routine is speed: When k = m, the
' effort to insert x(i) is proportional to log(m). When k
' < m, the effort to insert x(i) may be proportional just
' to k. The worst case would be when the array x was in
' ascending order since then x(i) would have to be inserted
' for each i. Similarly, in the case the array x is in
' descending order, after m inserts, no more inserts will
' be done. For the order of array x 'random', once a
' relatively large fraction of the m largest are in the
' heap, additional inserts become relatively rare.
'
' This routine is to be 'polymorphic', that is, to work for
' essentially any user defined class my_class1 where
'
' Dim m, n As Int32
' Dim x( n ) As my_class1
' Dim y( m ) As my_class1
'
' This routine can build an ascending heap, as discussed
' above, or a descending heap. The only difference is how
' the comparisons are made in the class used for the
' interface.
'
' The interface IComparer is used. If the usual class
' Comparer is used for this interface, then this function
' builds an ascending heap, that is, where upon return
'
' y( 1 ) <= y( j ),
'
' for j = 2, 3, ..., m.
Function obj_heap_insert( _
x As Object, _
y() As Object, _
ByRef k As Int32, _
m As Int32, _
compare As IComparer) As Int32
Dim routine_name As String = "obj_heap_insert"
Dim error_code As Int32
Dim return_code As Int32 = 0
' Dim result_code As Int32
Dim message_tag As Int32
Dim i_father As Int32
Dim i_child0 As Int32
Dim i_child1 As Int32
Dim i_child2 As Int32
Dim i_2 As Int32 = 2
Try
error_code = 1001
message_tag = 1001
If console_msg_level >= console_routine_messages2 Then _
Console.WriteLine( routine_name & " " & message_tag & _
": Started ..." )
error_code = 1002
If m <= 0 Then
return_code = 1001
Goto out
End If
If k < 0 Then
return_code = 1002
Goto out
End If
If k > m Then
return_code = 1003
Goto out
End If
If y.GetUpperBound(0) < m Then
return_code = 1004
Goto out
End If
error_code = 1003
If k < m Then
i_child0 = k + 1
k = i_child0
error_code = 1004
Do ' Sift value of x into correct position.
If i_child0 < 2 Then Exit Do
i_father = i_child0 \ i_2
error_code = 1005
If compare.Compare( x, y( i_father ) ) >= 0 Then Exit Do
y( i_child0 ) = y( i_father )
i_child0 = i_father
Loop ' Sift value of x into correct position.
error_code = 1006
y( i_child0 ) = x
Goto out
End If
error_code = 1007
If compare.Compare( x, y( 1 ) ) <= 0 Then Goto out
i_father = 1
error_code = 1008
Do ' Delete value of y( 1 ) and sift x to correct position
' starting at location y( 1 )
If i_father > m \ i_2 Then Exit Do
i_child1 = i_father + i_father
If i_child1 < m Then
i_child2 = i_child1 + 1
error_code = 1009
If compare.Compare( y( i_child1 ), y( i_child2 ) ) < 0 Then
i_child0 = i_child1
Else
i_child0 = i_child2
End If
Else
i_child0 = i_child1
End If
error_code = 1010
If compare.Compare( x, y( i_child0 ) ) <= 0 Then Exit Do
y( i_father ) = y( i_child0 )
i_father = i_child0
Loop ' Delete value of y( 1 ) and sift x to correct position
' starting at location y( 1 )
y( i_father ) = x
Catch
Console.WriteLine( " " )
message_tag = 1002
Console.WriteLine( routine_name & " " & message_tag & _
": Error condition raised. " & vbCrLf & _
": error_code = " & error_code & vbCrLf & _
": err.number = " & err.number & vbCrLf & _
": err.source = " & err.source & vbCrLf & _
": err.description = " & err.description )
message_tag = 1003
Console.WriteLine( routine_name & " " & message_tag & _
": Raising error condition with error_code = " & error_code )
err.raise(error_code, routine_name)
End Try
out:
message_tag = 1004
If console_msg_level >= console_routine_messages2 Then _
Console.WriteLine( routine_name & " " & message_tag & _
": Returning." )
Return return_code
End Function ' Function obj_heap_insertI'd be perfectly fine with just having to call StableSort vs Sort once in blue moon when I need it
If I had to do it again, I would make it stable now.
https://github.com/dart-lang/sdk/issues/433#issuecomment-108...