Merge Sort or Quick Sort for this problem? *****Please note I have only learned
ID: 3815018 • Letter: M
Question
Merge Sort or Quick Sort for this problem?
*****Please note I have only learned about Merge sort and Quick sort so the answer to the problem is one of these*****
1) You get a job with a small e-commerce company.
a) The company currently has 512,000 customers. The customer records are currently maintained in a list that fits into main memory. Each reference to a customer record takes up to 4 bytes. Your boss, Jorge, asks you to develop an algorithm to sort the list. The algorithm must be as fast as possible in most cases. You may, if necessary, use up to 1,000,000 bytes of additional memory for your algorithm. Which of the efficient sorting algorithms we discussed in class (merge sort or quick sort) could you use? Explain your answer.
b) The customer base has grown to 8,000,000 customers. You may need to reconsider your choice in part (a). Jorge now insists that the sorting algorithm must be as fast as possible in all cases, but the algorithm may now use up to 50,000,000 bytes of additional memory. Which of the sorting algorithms (merge sort or quick sort) could you use in this situation? Explain your answer.
Explanation / Answer
(1)(a) In the given scenario, I use Merge Sort algorithm as according to the question merge sort requires O(N) extra storage, Mergesort requires a lot more data copying. You need another temporary storage (typically the same size as your original data array) for the Merge function.
(1)(b) In the given scenario, I use Merge Sort algorithm as according to the question merge sort requires O(N) extra storage, Mergesort requires a lot more data copying. You need another temporary storage (typically the same size as your original data array) for the Merge function.This use a in-stable sorting. Quick sort doesn't use extra space.