# Mergesort vs Quicksort

Mergesort and Quicksort are both efficient sorting algorithms commonly used in computer science. Each has its own advantages and characteristics that make them suitable for different scenarios.

QuicksortMergesort
In-place sortingQuicksort is an in-place sorting algorithm, which means that it does not require any additional storage space to perform the sort. This is an advantage for large datasets, as it reduces the amount of memory that needs to be allocated.Mergesort is not an in-place sorting algorithm, which means that it requires additional storage space to perform the sort. This is because the algorithm must create temporary arrays to merge the sorted subarrays.
Stable sortingQuicksort is an unstable sorting algorithm, which means that it can sometimes change the order of equal elements in the input array. This is because the pivot element can sometimes cause equal elements to be moved to different sides of the partition.Mergesort is a stable sorting algorithm, which means that it preserves the order of equal elements in the input array. This is because the merging process is carefully designed to preserve the relative order of equal elements.
PerformanceThe worst-case time complexity of quicksort is O(n^2), where n is the number of elements in the array. This means that the algorithm can be very inefficient on certain types of input data.The best-case, average-case, and worst-case time complexity of mergesort are all O(n log n), where n is the number of elements in the array. This means that mergesort is guaranteed to be efficient on all types of input data.
FeatureQuicksortMergesort
In-place sortingYesNo
Stable sortingNoYes
Worst-case time complexityO(n^2)O(n log n)
Average-case time complexityO(n log n)O(n log n)
Best-case time complexityO(n log n)O(n log n)