448
Marge sort (lemmy.ml)
top 19 comments
sorted by: hot top controversial new old
[-] lockhart@lemmy.ml 66 points 2 months ago

well I think it's pretty neat

[-] DarkDarkHouse@lemmy.sdf.org 3 points 1 month ago

It even runs on my potato server

[-] Successful_Try543@feddit.org 28 points 2 months ago
[-] creamlike504@jlai.lu 26 points 2 months ago

I was with you until the last step. How did it all get sorted, instead of having two "peaks"?

[-] xorollo@leminal.space 27 points 2 months ago

https://en.m.wikipedia.org/wiki/Merge_sort

The video animation shows what is going on when you merge two lists together. You're comparing the first two indices and sorting them to complete that step.

[-] creamlike504@jlai.lu 27 points 2 months ago

Thank you! I now understand the joke.

[-] Hupf@feddit.org 2 points 2 months ago* (last edited 2 months ago)
[-] shnizmuffin@lemmy.inbutts.lol 8 points 2 months ago

I'm pretty sure it's because the sort comparison is between the indexes of each array, and happens at every step.

[-] davidgro@lemmy.world 17 points 2 months ago

Then what is the purpose of the middle steps?
Second to last also has this problem.

The image has big "Draw the rest of owl" energy.

[-] homura1650@lemm.ee 14 points 2 months ago* (last edited 2 months ago)

I think the image assumes that the viewer is familiar with merge sort, which is something you will learn in basically every undegraduate CS program, then never use.

To answer your first question, it helps to have something to compare it against. I think the most obvious way of sorting a list would be "insertion sort", where you look through the unsorted list, find the smallest element, put that in the sorted list, then repeat for the second smallest element. If the list has N elements, this requires you to loop through it N times. Since every loop involves looking at N elements, this means you end up taking N * N time to sort the list.

With merge sort, the critical observation is that if you have 2 sublists that are sorted you know the smallest element is at the start of one of the two input lists, so you can skip the inner loop where you would search for the smallest element. The means that each layer in merge sort takes only about N operations. However, each layer halves the number of lists, so you only need about log_2(N) layers, so the entire sort can be done in around N * log(N) time.

Since NlogN is smaller then N^2, this makes merge sort theoretically better.

[-] skibidi@lemmy.world 10 points 2 months ago

Note: N^2 and NlogN scaling refer to runtime when considering values of N approaching infinity.

For finite N, it is entirely possible for algorithms with worse scaling behavior to complete faster.

[-] davidgro@lemmy.world 2 points 2 months ago

That does make more sense when explained that way, thank you.

[-] uranibaba@lemmy.world 6 points 2 months ago

Feels like the one who created this didn't want to do step 3 to 5 for all levels.

[-] Karl@programming.dev 9 points 2 months ago

I take pride in understanding a joke in programminghumor for the first time. (I just started with computer-science)

[-] SatouKazuma@programming.dev 3 points 2 months ago

Oof you picked the wrong field. Honestly, programmer culture is elitist and toxic as fuck, speaking as someone who made that mistake before.

[-] Karl@programming.dev 1 points 2 months ago

Why do you think I would want to know if I picked the wrong field?

[-] hedge_lord@lemmy.world 9 points 2 months ago
[-] pewgar_seemsimandroid 6 points 2 months ago
[-] PattyMcB@lemmy.world 3 points 2 months ago

-Marge groan-

this post was submitted on 07 May 2025
448 points (100.0% liked)

Programmer Humor

24937 readers
1304 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

founded 2 years ago
MODERATORS