list-sort(3scm)

✨ list-sort, vector-sort — stable sorting of lists and vectors ✨

okay bestie, you know how sorting is like, the most main-character thing in all of programming? yeah. this is that. this is list-sort(3scm) from the Scheme Programmer's Manual and it's giving organized chaos. 🎀

📚 LIBRARY 📚

so like, you gotta import these bad boys first, iykyk:

(import (rnrs))                     ;R6RS
(import (rnrs sorting))             ;R6RS

🦋 SYNOPSIS 🦋

here's the whole vibe, the shape of it:

(list-sort proc list)
(vector-sort proc vector)

two functions. one for lists, one for vectors. iconic behavior. 💅

🌸 DESCRIPTION 🌸

so list-sort and vector-sort perform a stable sort of your list or vector in ascending order according to proc. like, they take your messy little collection and hand it back to you all glowing up. ✨

the proc is the rulebook, okay? it should accept two elements and return a true value when its first argument is strictly less than its second, and #f otherwise. that's the whole job. that's it. easy. 🫶

⏱️ Time complexity ⏱️

the sorting algorithm performs O(n lg n) calls to proc, where n is the length of list or vector. no cap, that's the complexity. ngl that's pretty slay of them.

🙈 Side effects 🙈

literally do NOT give proc side effects bestie. the pairing of arguments and the sequencing of calls to proc are not specified — so like, you don't get to control which elements get compared when, k? the algorithm is the main character here, not you. 😭

good news though: the sorting algorithm does not modify list or vector. your original data is safe and untouched. periodt. 💖

🧚 IMPLEMENTATION NOTES 🧚

okay this part is such tea. ☕

• Quicksort cannot be used because it has worse time complexity than what is required.
• Heapsort cannot be used either because it is not stable. 💀
• Merge sort satisfies all requirements and can be used — but it is not the only option.

so like, merge sort is the safe pick, but the door's open if you're feeling creative. slay.

👑 RETURN VALUES 👑

both of these procedures return a single value. the list-sort procedure returns a list, and vector-sort returns a vector. classic.

the return value may be eq? to the argument when the argument is already sorted (like, if it's already perfect, they just hand it back to you — generous queens 🌈), and the list returned by list-sort may share structure with a tail of the original list. so like, heads up, they're close. 🫶

also: if multiple returns occur from list-sort or vector-sort, the return values returned by earlier returns are not mutated. good behavior. we stan. 🙈

🔥 EXAMPLES 🔥

honestly? study these. they ate:

(list-sort < '(3 5 2 1))     =>  (1 2 3 5)
(vector-sort < '#(3 5 2 1))  =>  #(1 2 3 5)

see how 3 5 2 1 becomes 1 2 3 5? that's the work. that's literally the work. ✨

🌈 COMPATIBILITY 🌈

these procedures are unique to R6RS. and if you're out here like "but bestie what about alternatives," don't worry, they're available in SRFI-95 and SRFI-132. you got options, iykwim. 💅

💀 ERRORS 💀

this procedure can raise exceptions with the following condition types:

• &assertion (R6RS) — the wrong number of arguments was passed or an argument was outside its domain. in particular, proc should accept two arguments, which are elements from list or vector, and return one value. like, don't play with it. the vibe check will fail. 😭

🎀 SEE ALSO 🎀

vector-sort!(3scm) — the sibling, the one with the bang. go say hi. 👋

⭐ STANDARDS ⭐

R6RS. that's the standard, bestie. it's giving official. 👑

🍓 HISTORY 🍓

these procedures first appeared in R6RS. so they're not ancient, but they're also not new. they're just... them. 💜

💖 AUTHORS 💖

this page is part of the scheme-manpages project. it includes materials from the RnRS documents. more information can be found at https://github.com/schemedoc/manpages/. go check it out fr fr. 🫶

---

💅 that's a wrap, bestie! list-sort(3scm) — Scheme Programmer's Manual, dated 2023-01-25. sort responsibly. ✨