Curios why we are using

int midpoint = (start + end) / 2; // overflow issue when end is Integer.MAX_VALUE

instead of

int midpoint = start + (end - start)/2;

I think we should also mention that that the maximum recursion layer is O(n) in the worst case when the list is already sorted so the space complexity in the worst case is also O(n).

Can comments be added to code blocks to convey the pseudocode that supports it

Thank you for pointing this out

Quick sort: In Python

do we need extra start_ptr < end_ptr for line 10 and line12â€¦?

Yes, it is a break condition for the inner while loop

Pythonic merge sort version:

def merge_sort(array: list[int]) â†’ list[int]:

if len(array) < 2:

return array

else:

mid = len(array)//2

left = merge_sort(array[:mid])

right = merge_sort(array[mid:])

return merge(left, right)

def merge(left: list[int], right: list[int]) â†’ list[int]:

result = []

while len(left) > 0 and len(right) > 0:

if left[0] <= right[0]:

result.append(left.pop(0))

else:

result.append(right.pop(0))

result += left

result += right

return result

pythonic quick sort version:

def quick_sort(array: list[int]) â†’ list[int]:

if len(array) < 2:

return array

else:

pivot = array[0]

less = [i for i in array[1:] if i <= pivot]

greater = [i for i in array[1:] if i > pivot]

return quick_sort(less) + [pivot] + quick_sort(greater)

Btw, here is ChatGPT answer in javascriptâ€¦ You canâ€™t beat this! Concise and beautiful

function quicksort(arr) {

if (arr.length <= 1) return arr;

let pivot = arr[arr.length - 1];

let left = [];

let right = [];

for (let i = 0; i < arr.length - 1; i++) {

if (arr[i] < pivot) {

left.push(arr[i]);

} else {

right.push(arr[i]);

}

}

return quicksort(left).concat([pivot], quicksort(right));

}

But sadly this example code, it is not inplace sorting, which is the main selling point of Quick sort over merge sort, even though it has n^2 worst case, but with this code, it uses the extra space as merge sort and has poor worst case complexity

Againâ€¦the example code is terrible! Its as if the authors had never written code mean to be read by other humans.

Try this for merge sort:

```
class Solution:
def merge(left_half, right_half):
left_idx, right_idx = 0,0
result = []
while left_idx < len(left_half) and right_idx < len(right_half):
if left_half[left_idx] < right_half[right_idx]:
result.append(left_half[left_idx])
left_idx += 1
else:
result.append(right_half[right_idx])
right_idx += 1
while left < len(left_half):
result.append(left_half[left_idx])
left_idx += 1
while right < len(right_half):
result.append(right_half[right_idx])
right_idx += 1
return result
def sortArray(self, nums: List[int]) -> List[int]:
if len(nums) <= 1:
return nums
middle = len(nums) // 2
left_half = self.sortArray(nums[:middle])
right_half = self.sortArray(nums[middle:])
return merge(left_half, right_half)
```

I need help with merge sort

```
function sortList(unsortedList) {
const n = unsortedList.length;
if (n <= 1) return unsortedList;
const midpoint = Math.floor(n / 2);
const leftList = sortList(unsortedList.slice(0, midpoint));
const rightList = sortList(unsortedList.slice(midpoint));
const res = [];
let leftPtr = rightPtr = 0;
while (leftPtr < midpoint || rightPtr < n - midpoint) {
if (leftPtr === midpoint) {
res.push(rightList[rightPtr]);
rightPtr++;
} else if (rightPtr === n - midpoint) {
res.push(leftList[leftPtr]);
leftPtr++;
} else if (leftList[leftPtr] <= rightList[rightPtr]) {
res.push(leftList[leftPtr]);
leftPtr++;
} else {
res.push(rightList[rightPtr]);
rightPtr++;
}
}
return res;
}
```

why are we doing rightPtr < n - midpoint ? what does it even mean ??

Can we have comments within the code plzzz. If anyone wrote code like this in the workplace, theyâ€™d be admonished

only thing about this quicksort example that differs from the one provided is its not in place since its using new lists for less and greater. I think this would be a comparable in place version.

def quick_sort(arr, start, end):

if start < end:

pivot = partition(arr, start, end)

quick_sort(arr, start, pivot - 1)

quick_sort(arr, pivot + 1, end)

return arr

def partition(arr, start, end):

pivot = arr[end]

i = start

for j in range(start, end):

if arr[j] <= pivot:

arr[i], arr[j] = arr[j], arr[i]

i += 1

arr[i], arr[end] = arr[end], arr[i]

return i

```
if end - start <= 1:
```

for quick sortâ€¦

^^ shouldnâ€™t that be end - start <= 0: since if the different is 1 that means there are 2 elements and they could be unsorted?