search

emory-courses / dsa-java

Data Structures and Algorithms in Java
https://emory.gitbook.io/dsa-java/
42 stars 55 forks source link

Sorting Algorithms #43

Closed ddalama closed 4 years ago

ddalama commented 4 years ago

Hello,

If QuickSort and MergeSort have the same average-case complexity (n log(n)) and MergeSort's worst-case complexity is better, why is QuickSort more popularly used?

Also, in textbook section 3.1, in the method sort(T[ ] array), when we call sort(array, 0, array.length), I don't understand why we write array.length and not (array.length - 1), since the last index of 'array' would be (array.length - 1). Could you please clarify my confusion?

Thanks.

marvinquiet commented 4 years ago

IMO, QuickSort does not need external storage to finish the sorting when the memory is limited.

lujiaying commented 4 years ago 
/**
 * Sorts the array[beginIndex:endIndex].
 * @param array      an array of comparable keys.
 * @param beginIndex the index of the first key to be sorted (inclusive).
 * @param endIndex   the index of the last key to be sorted (exclusive).
 */
abstract public void sort(T[] array, int beginIndex, int endIndex);

For second question: The @param endIndex in https://emory.gitbook.io/dsa-java/sorting-algorithms/abstraction defines endIndex as an exclusive index.