Programmer Humor

22354 readers

2600 users here now

Welcome to Programmer Humor!

This is a place where you can post jokes, memes, humor, etc. related to programming!

For sharing awful code theres also Programming Horror.

Rules

Keep content in english
No advertisements
Posts must be related to programming or programmer topics

founded 2 years ago

MODERATORS

[email protected]

726

Dev Interviews (lemmy.ml)

submitted 5 days ago by [email protected] to c/[email protected]

42 comments fedilink hide all child comments

https://turnoff.us/geek/dev-interviews/

you are viewing a single comment's thread
view the rest of the comments

[–] [email protected] 2 points 4 days ago (1 children)

For the most part it’s best to use system provided sorting implementations, but somebody has to write those implementations, so every once in a while somebody needs to do it (in practice by looking up a reference implementation of course).

But also it’s good to understand things like big O scaling and why we use quicksort rather than a naive insertion sort and when to use quick sort vs merge sort or some other form of stable sort.

[–] [email protected] 1 points 3 days ago* (last edited 3 days ago)

Glibc's qsort will default to either insertion sort mergesort or heapsort. Quicksort itself is used when it cannot allocate extra memory for mergesort or heapsort. Insertion sort is still used in the quicksort code, when there is a final 4 items that need to be sorted.

Normally it is simply mergesort or heapsort. Why I know this? Because there was a recent CVE for quicksort and to reproduce the bug I had to force memory to be unable to be allocated with a max size item. It was interesting reading the source code.

That is if you are not on a recent version of qsort which simply removed quicksort altogether for the mergesort + heapsort

Older version still had quicksort and even some had insertion sort. Its interesting to look at all the different versions of qsort.