If anyone got time, can you teach me merge sort or quick sort?

[uncut carbon]

I can teach you merge sort @ruby solstice

i think the easiest way to understand is starting with the merging part.

let's say you have an array like.... 6 1 5 4 3 2
the first step which i'm gonna gloss over a bit is to split it into smaller arrays. When you finish the first step, you are left with one array that contains just 6, one that just has 1, one that just has 5, and so on.

then what you do is you "merge" every two arrays together

the first two arrays are [6] and [1]

when you merge, you basically say you're gonna make a new array. And you're going to take an element from one of the two arrays you have based on which number is smaller.

1 is smaller than 6, so the first element in your new array is [1], then you put the 6 in, so you get the new array [1 6]

then for the next two arrays, [5] and [4]... if you merge these together, you get [4 5]

so now you have two arrays, [1 6] and [4 5]

for the next level of merge, you merge these two together by starting at the beginning of each array and asking first... is 1 less than 4? yes so I take 1... [1]
is 6 less than 4? no so I take the 4... [1 4]
is 6 less than 5? no so I take the 5... [1 4 5]
and the only thing left is 6 so I take the 6 finally. ... [1 4 5 6]

So if you want to write a merge sort function, the first thing you do is write a merge() function which takes two arrays and merges them with that algorithm.
merge([1, 6], [4, 5]) --> [1 4 5 6]

The key thing about merge() is that the two arrays it is merging have to already be sorted.

Which is always the case, because the two arrays it merges are the result of merging other two arrays.

Now for the trickiest part to understand.

The first step which I glossed over is you start with an array [6 1 5 4 3 2] and you have to split it into smaller arrays... but how?

The general way it's done is:

1. You split the array in half
2. You sort each half
3. You merge the two sorted halves.

How do you do step #2? Well, you split each half in half. And sort each of those halves. And then merge them.

So that's the part that is recursive. mergeSort() can be thought of as:

1. Split the array in half
2. mergeSort() each half
3. merge() the two sorted halves

The recursive call to mergesort() will do those steps 1-3 again but for the half. So you end up splitting each half in half, again and again, until you have only one element in each array, which is the base case.

The base case is when the half you give to mergeSort() only has one element, you do not need to split it in half and sort anymore, because an array with one element is already sorted.

I hope this helps!

Sequentially, you can think of the algorithm as splitting the array in half over and over until they are each 1 element long, then merging them over and over. This is because if you actually follow the execution of the code, it looks like this:

1. Split array in half
2. Call mergeSort(), which means it will first perform step #1 split the half in half
3. Then calls mergeSort() on each half-of-half - and what THAT mergeSort call does first is split the half-of-half in half
4. Then calls mergeSort() on each half-of-half-of-half - and what THAT does first is split each of those in half.
   ... All the way until you reach the base case. The base case then RETURNS, which allows each mergeSort() call to proceed to the merge() step. So then the deepest call will merge() and return, then the call before that will merge() and return, and so on up to the top level.

[tribal cypress]

cheryllium you've been given 8 kudos from rs.ftb.

[turbid snow]

That was a really good explanation

[uncut carbon]

Merging an odd length sublist with an even length one should work the same way... no reason the algorithm should work any different. You just keep taking the lower number out of each list until you have one left, then you take the number you have left.

Umm, @ruby solstice I may need to see your code to see why it has this problem. There should be nothing special you need to do to make the odd/even case work

You don't need recursion for the merging part, but you do need to call mergeSort recursively like I explained above.

You won't get any depth error for any array you test this with.

Sorry, but it's just incorrect to do merge sort without recursion. It is commonly taught as a great example of a recursive algorithm. I would rewrite this to be recursive so you can learn it properly.

It's an algorithm that can be written most simply by using recursion, as well. Doing it with recursion results in the most readable code.

You are not going to run into any problem with the recursion depth in Python, trust me. I'm assuming you are doing this in order to learn the algorithm, so you should learn it properly.

If you are actually making something in Python and need to sort an array, you would use a built-in sort function to do that, not write your own merge sort. So writing your own merge sort is just an exercise in learning it, it makes sense to do it the right way.

Well, if you are looking for an iterative sorting algorithm only, merge sort is not the right choice for your library.

Okay, I take that back. You can of course write any recursive code iteratively

I'm not sure why you need to write your own sort, but Python's sort uses this https://en.wikipedia.org/wiki/Timsort

But yeah, I hear you

@ruby solstice So, I don't have a lot of experience with iterative merge sort, but I would do a little research on this if I were you because it is pretty complicated to do it iteratively. I'm not sure if I can explain it clearly. But basically:

1. You need a variable to keep track of the length of sub-arrays you are merging. (This variable should start at 1)
2. Go through the array and merge each sub-array of these lengths, copying the new values back into the array. (Make a copy of the array before all this if you don't want it to be destructive.)
3. Double the length.
4. Do steps 1-3 repeatedly in a while* loop until the length of the sub array has equaled or exceeded the length of the original array (that is, you now have one sorted array)
   You must write additional code that checks for the edge cases of when the sub-arrays go outside of the array.

@ruby solstice I take back what I said earlier, I just didn't understand why you were doing this and I also spoke too hastily and was wrong that you shouldn't use it. You can use iterative merge sort for your library, it's not a bad choice given its time complexity. Just be aware it's a lot harder to understand and implement iteratively. It's a divide-and-conquer algorithm which makes it very intuitive to understand recursively. But the steps I gave above should get you there.

Yeah, good luck haha. Also I would write it recursively first too just so you learn it and get the joy of writing it recursively, lol. It's really satisfying to write recursively because the code ends up being so simple and neat.

[proud marsh]

You won't get it unless your list is like 2^1000 elements or longer

At that point I think your memory would blow first lol

[proud marsh]

@ruby solstice I can explain quick sort if you still want one

[proud marsh]

Well the height of your recursive tree is log2(n) so if 1000 = log2(n) then n = 2^1000

Unless I misunderstood recursive depth limit

Each time your merge sort splits the partition into two

So if you assume your original list is some 2^x length

Then you have x times it'll split

• or - 1 I can't remember

16 -> 8 -> 4 -> 2 -> 1

Oh that's 4 splits and 16 = 2^4

Well x-1 if you consider your base case to be a list of length 2 or fewer

I'm not sure what you mean by "more considerate" and "preparing the base case"

Ngl I don't know the iterative merge sort

https://stackoverflow.com/questions/66695718/why-is-recursive-merge-sort-preferred-over-iterative-merge-sort-even-though-the

I think it's not clear which is better

uhhhhh

They're both asymptotically the same

O(nlogn) time and O(n) space

Lmao

That's why I've never tried to do it iteratively cause the recursive was is so easy to understand and implement

I've only written it like twice cause the only time you're asked to implement a sorting algorithm is like in a course or if you have some wack scenario 😂

I mean that's true

At least understand them conceptually and also how to analyse the runtimes

Big O isn't too difficult

Oh yeah I was supposed to explain quick sort

Given a list, what you do is you choose one element to be what's called a pivot. After choosing that pivot, you grab all the elements in the list that is smaller than the pivot and put it to the left (I'm explaining ascending order but whatever) and everything greater to the right

Now your pivot is in the correct place

Then you repeat with the left and right partitions

(this one easier with recursion as well because it's a divide and conquer algorithm)

It is imo lol

I don't think that's the reason lol

Cause asymptotically the worst case is slower than merge sort lol

You just gotta practice. Also, being able to visualise the recursion tree and each state makes it easier in my opinion

Yeah that's the kinda thing I see in my head when I think of merge sort

I'd say I'm average lol

I struggled quite a bit in my algorithms course I just did

Greedy algorithms, randomised algorithms, network flows, dynamic programming, divide and conquer, and others I can't remember

It was more focussed on like algorithmic paradigms instead of specific algorithms

Although we did learn specific ones

That's why all the big money places do technical interviews lol