Open Menu
AllLocalCommunitiesAbout
lotide
AllLocalCommunitiesAbout
Login

Marge Sort

⁨417⁩ ⁨likes⁩

Submitted ⁨⁨3⁩ ⁨months⁩ ago⁩ by ⁨fossilesque@mander.xyz⁩ to ⁨science_memes@mander.xyz⁩

https://mander.xyz/pictrs/image/b735d4bb-1806-4f54-9dc0-af8dab1f1b4a.png

source

Comments

Sort:hotnewtop
  • Eheran@lemmy.world ⁨3⁩ ⁨months⁩ ago

    How does the last step sort an of the sizes? Why even have all the other steps if that one can do it all?

    source
    • SmoothLiquidation@lemmy.world ⁨3⁩ ⁨months⁩ ago

      When you merge two sorted lists, you only have to compare the first element of each, since you can trust that all of the other elements are bigger. All the steps before that are there to make sure that is true.

      source
      • IrateAnteater@sh.itjust.works ⁨3⁩ ⁨months⁩ ago

        Wait, how do I know that all four of the right half aren’t smaller than all four of the Left half?

        source
        • -> View More Comments
    • Ravi@feddit.org ⁨3⁩ ⁨months⁩ ago

      The one and only way to learn sorting algorithms: youtu.be/dENca26N6V4?si=pDZoR0uRiuGoqwkr

      source
      • bitjunkie@lemmy.world ⁨3⁩ ⁨months⁩ ago

        I’d watch this if I didn’t know about programming just for the sheer weirdness

        source
    • Iron_Lynx@lemmy.world ⁨3⁩ ⁨months⁩ ago

      If you want to zipper two sorted lists, you compare the first element of each list, pick that first, take the next element of that list, rinse & repeat until one list runs out and then just chuck the entire rest of the other list in the remaining space, even if that’s just one element. Since your two initial lists are already sorted, you can trust the combined list to also be sorted.

      source
      • Eheran@lemmy.world ⁨3⁩ ⁨months⁩ ago

        So the point is that always only exactly 2 elements are compared and so you first have to split everything into groups of 2. Seems very inefficient for larger datasets, since you need to handle every single item over and over again and compare so so often. But not a sorting and comparison expert, so no idea if human sorting logic applies at all.

        source
        • -> View More Comments
    • CaptainBlagbird@lemmy.dbzer0.com ⁨3⁩ ⁨months⁩ ago

      youtu.be/es2T6KY45cA

      source
  • cholesterol@lemmy.world ⁨3⁩ ⁨months⁩ ago

    Step 4 seems to do nothing?

    source
    • Fiery@lemmy.dbzer0.com ⁨3⁩ ⁨months⁩ ago

      Step 4 splits the pair above into single elements, from step 5 on the groups are getting merged.

      source
      • Lemmine@feddit.org ⁨3⁩ ⁨months⁩ ago

        *Marged

        source
        • -> View More Comments
      • cholesterol@lemmy.world ⁨3⁩ ⁨months⁩ ago

        Oh right, okay.

        source