Self Doubt

Question

Please correct if any of the point is wrong :

Quicksort:
1.Need more random accesses

2 Used when Random access is fast (hence preferred on array and not on Linked List)

2 No extra space needed ==> Inplace

4 Not a stable sorting algorithm

5 even in worst case using randomized quick sort (O(n^2)

MergeSort:

1 Need Less random accesses than quicksort

2 Preferred When random access is very slow(On linked list)

3 why Not preferred for array over quicksort ?? ==> Extra space needed auxillary array O(N)

4 Extra space needed when applied on Array | No extra space needed when applied on Linked List

4 Stable sorting algo

Somone please explain this point its from geeksforgeeks:

Quicksort in particular exhibits good cache locality and this makes it faster than merge sort in many cases like in virtual memory environment.

Comments

@jatin khachane 1

where do u get these lines?

I mean quick sort always not require random access

right?

Are these lines from cormen?

---

I think randomized quick sort takes time $O(n^{2})$

https://gateoverflow.in/707/gate2001-1-14

---

no ma'am i just wrote my understanding please correct if something wrong

---

TC is not right

---

edited ..ma'am rest is ok ?

---

Quick sort is Not a stable sorting algorithm

 need to work on this.... i mean in my opinion we can make sure it as a stable algorithm.. but i will check it

---

how many comparisions quick sort and merge sort have in avg and worst case ?

---

Quick sort is Not a stable sorting algorithm

 need to work on this.... i mean in my opinion we can make sure it as a stable algorithm.. but i will check it

yes, quicksort isn't stable. you may refer if you want

 

how many comparisions quick sort and merge sort have in avg and worst case ?

is it self doubt ?

---

actually m confused what is parameter because quick sort is preffered over merge sort while input is in array

---

Quicksort usually is better than mergesort for two reasons:

1. Quicksort has better locality of reference than mergesort, which means that the accesses performed in quicksort are usually faster than the corresponding accesses in mergesort.

2. Quicksort uses worst-case O(log n) memory (if implemented correctly), while mergesort requires O(n) memory due to the overhead of merging.

Source: https://stackoverflow.com/questions/29218440/when-merge-sort-is-preferred-over-quick-sort