🏫 [CS50x 2025] 3 Sort

⏰ Time Complexity

🔥 Big O (O) - Upper Bound

“No matter what, the algorithm won’t be worse than this.”

• Example: O(n²)
• Means: In the worst case, the running time grows no faster than n².
• Think of it like: “At most, my algorithm will behave this badly.”

---

🔥 Big Omega (Ω) - Lower Bound

“No matter what, the algorithm will at least be this fast.”

• Example: Ω(n)
• Means: In the best case, the running time won’t be better than n.
• Think of it like: “At least, it’ll take this much time.”

---

🔥 Big Theta (Θ) - Tight Bound

“This is exactly how my algorithm grows - neither better nor worse.”

• Example: Θ(n log n)
• Means: The running time grows exactly like n log n for large inputs.
• Think of it like: “This is my algorithm’s true speed, no matter the case.”

---

👨🏻‍🏫 Summary

1. O - describes the worst-case.
2. Ω - shows the best-case.
3. Θ - nails down the real growth rate (if the upper and lower bound are the same).

---

❓ Recursive Loop - When exactly does it start to draw?

int main(void)
{
    int height = get_int("Height: ");
    draw(height);
}

void draw(int n)
{
    if (n <= 0)
    {
        return;
    }

    draw(n - 1);

    for (int i = 0; i < n; i++)
    {
        printf("#");
    }
    printf("\n");
}

Let’s walk through this code line by line, literally like time-traveling with the program flow 👇:

---

void draw(int n)
{
    if (n <= 0)   // 1️⃣ Check if we're done.
    {
        return;   // 2️⃣ If n <= 0, stop everything.
    }

    draw(n - 1);  // 3️⃣ FIRST, go *deeper* (this delays printing!)

🚨 At this point, it does not draw yet! It just keeps calling draw(n-1) again and again:

draw(3)
 └── draw(2)
      └── draw(1)
           └── draw(0) → returns immediately (base case)

At draw(0) - 🛑 STOP. Nothing prints. But now… the stack starts to unwind.

---

🖌 Now the real drawing starts:

The moment we hit the base case and return, the calls start finishing in reverse order:

Call	What happens after returning?
draw(1)	Prints 1 #
draw(2)	Prints 2 ##
draw(3)	Prints 3 ###

    for (int i = 0; i < n; i++)   // 4️⃣ NOW starts drawing
    {
        printf("#");
    }
    printf("\n");
}

So:

1. Deep dive first 🏊 - nothing prints while going deeper.
2. Print while coming back up 🏔 - each level draws.

---

👑 Exact Moment of Drawing:

• ✅ First actual print happens only AFTER hitting the base case (n == 0) and returning to n == 1.
• ❌ No printing happens during the dive down.

That’s why it feels delayed. It’s how recursion works: it stores the tasks, postpones them until it’s time to “climb back up.”

❓ Why I Cannot Use == to Compare if Two Strings Have the Same Content in C

💥 Why Not?

In C, strings are actually just pointers to the first character in a character array (char *). So when you write:

if (str1 == str2)

You’re not comparing the content of the strings - you’re comparing whether the pointers point to the same memory location.

So this only returns true if str1 and str2 are literally the same address, which is usually not what you want.

---

✅ What to Use Instead?

Use strcmp() from the standard library string.h:

#include <stdio.h>
#include <string.h>

int main() {
    char str1[] = "hello";
    char str2[] = "hello";

    if (strcmp(str1, str2) == 0) {
        printf("They are the same!\n");
    } else {
        printf("They are different!\n");
    }

    return 0;
}

strcmp() returns 0 when the strings are equal. That’s what you check for.

---

📧 About the Same Address

When you write this in C:

if (str1 == str2)

You’re not asking:

“Do these two strings say the same thing?”

You’re really asking:

“Do these two strings live in the exact same spot in memory?”

---

💡 Think of it Like This:

Imagine you wrote two love notes that both say “I love you” - but one is hidden in your diary 📖 and the other’s tucked inside your hoodie pocket 🧥.

Now, you ask:

• == checks if both notes are in the same place (like both in the diary).
• strcmp() checks if both notes say the same thing, no matter where they are.

So unless both strings are the same piece of paper in memory, == says ❌ “Not equal.”

But strcmp() lovingly reads them both and says 💖 “Yes, same words, same feelings.”

---

👀 Quick Demo:

char *a = "kiki";
char *b = "kiki";
char c[] = "kiki";
char d[] = "kiki";

printf("%s\n", a == b ? "same address" : "diff address"); // might print "same"
printf("%s\n", c == d ? "same address" : "diff address"); // will print "diff"

Why? Because string literals might get stored in the same place, but arrays always get their own little memory bed.

---

🥜 char *a vs char a[] - What’s the Deal?

🔹 char a[] = "kiki";

This creates an array in memory. The characters k, i, k, i, and the ending \0 get stored inside the variable a - they live inside that memory spot. Think of it like this string gets its own lil’ room 🛏️ in memory.

🔹 char *a = "kiki";

This creates a pointer to the string literal "kiki" - a place in memory that C manages for you (read-only most of the time). a just points to that string. It’s like a sticky note that says “yo, the string lives over there 👉”.

So:

• a[] = room with string inside it
• *a = a hand pointing to a string that lives somewhere else

---

🛠 What Happens Behind the Curtain?

char *a = "kiki";
char *b = "kiki";

C might optimize this by storing both "kiki"s in the same memory spot (literal pooling). So a == b might be true, which can be confusing for beginners!

But:

char a[] = "kiki";
char b[] = "kiki";

💡 What Is Literal Pooling?

Literal pooling (also called string interning in other languages) is when the compiler saves memory by reusing the same string literals that appear more than once in your code.

So if you write:

char *a = "sneaky"; 
char *b = "sneaky";

Instead of making two separate "sneaky"s in memory, the compiler might go:

“Hmm… no need to store this twice. Let’s make one "sneaky" and just point both a and b to it.”

✨ Boom - both a and b point to the same memory address.

---

🔍 Why It Matters?

Because of this:

if (a == b)

• You might get true not because the strings are “equal”, but because they live at the same memory location, thanks to literal pooling.

😵 Sneaky, huh? That’s why you never use == to compare strings - even if sometimes it “works” and sometimes it doesn’t.

---

🧪 But Wait… Does This Always Happen?

• C can do literal pooling, but it’s not guaranteed by the C standard.

• It depends on:

  • Compiler behavior (like gcc, clang)
  • Optimization flags (like -O2)
  • Whether the strings are modded or not (e.g., "kiki" vs "KiKi")

That’s why:

char *a = "kiki";
char *b = "kiki";

Might give you:

a == b → true

But:

char a[] = "kiki";
char b[] = "kiki";

Always:

a == b → false (two separate arrays)

🍪 Merge Sort

🧠 First: What is Merge Sort?

Merge sort is like a divide & conquer algorithm - it keeps splitting the numbers into smaller groups until each group has just one number, then it starts merging them back in order.

Think of it like:

Breaking a cookie into crumbs 🍪➡️ then sticking them back together into a more perfect cookie 🍪 but now in number order.

---

🪜 Let’s Walk Through This Example: 6341

We want to sort these digits:

6 3 4 1

---

🔪 Step 1: Divide Phase (recursive breakdown)

Split in half each time until you hit 1 number per group.

[6 3 4 1]       ← start here
   /   \
[6 3]  [4 1]    ← split into 2 halves
 / \     / \
[6][3] [4][1]   ← split again until each has 1 number

---

🧵 Step 2: Merge Phase (sort while merging)

Now we start merging back in sorted order:

Merge [6] and [3] → [3 6]

Because 3 is smaller than 6.

Merge [4] and [1] → [1 4]

Because 1 is smaller than 4.

Now we have:

[3 6] and [1 4]

1. 🔍 Compare 3 (left) vs 1 (right) 👉 1 is smaller → put 1 into the result array

   🪄 Result so far: [1]

2. 🔍 Compare 3 (left) vs 4 (right) 👉 3 is smaller → put 3 into the result

   🪄 Result so far: [1, 3]

3. 🔍 Compare 6 (left) vs 4 (right) 👉 4 is smaller → put 4 into the result

   🪄 Result so far: [1, 3, 4]

4. Only 6 is left on the left side (no more right!) 👉 Just copy it over

   🪄 Final Result: [1, 3, 4, 6]

---

💘 Quick ASCII Animation:

Left:   3 6
Right:  1 4
Result: -

Compare 3 vs 1 → take 1       → [1]
Compare 3 vs 4 → take 3       → [1, 3]
Compare 6 vs 4 → take 4       → [1, 3, 4]
Nothing left on right → take 6 → [1, 3, 4, 6]

---

🧠 Bonus: Merge Rule

Always compare the first element of left with the first element of right. Take the smaller one, add it to result, and move that pointer forward.

This is why it’s called “merge” - it weaves two sorted lists into one sorted one.

---

🧠 Time Complexities of Common Sorting Algorithms

Sort Type	Best Case (Ω)	Average Case (Θ)	Worst Case (O)	Space	Stable?
Bubble Sort	Ω(n)	Θ(n²)	O(n²)	O(1)	✅ Yes
Selection Sort	Ω(n²)	Θ(n²)	O(n²)	O(1)	❌ No
Merge Sort	Ω(n log n)	Θ(n log n)	O(n log n)	O(n)	✅ Yes

---

💎 Bubble Sort

• Swaps adjacent elements until everything is sorted.
• Best Case (already sorted): Ω(n)
• Worst Case (reverse order): O(n²)
• Notes: Cute for learning. Pathetically slow in practice. Only cute if you’re a baby array. 👶🫧

---

💎 Selection Sort

• Finds the smallest item, puts it first. Then next smallest. Like choosing prom queens one by one.
• Always O(n²) because it scans the whole list every time, even if sorted 😑
• Not stable (doesn’t preserve original order of same-value items).

---

💎 Merge Sort

• Uses divide and conquer - splits the list, sorts each side, then merges them together.
• Always O(n log n) - even on best case!
• Extra space needed for merging 🧠
• But it’s stable, predictable, and used in real-life libs (like Timsort based on it).

---

🥷 Which One to Use?

You’re Sorting…	Use…
Tiny array or learning the basics	Bubble or Selection (just for fun)
Want consistency + performance	Merge Sort
Can’t use extra memory (in-place only)	Selection Sort maybe… 🥲
Real-world large data (Python/Java)	Timsort (based on merge + insertion)