Scribd
Upload
6 views1 page

Sort Algorithm

The document compares various sorting algorithms: Merge Sort, Radix Sort, and Quicksort, detailing their time and space complexities, stability, in-place status, and best use cases. Merge Sort is stable and efficient for small datasets, while Radix Sort excels with limited digit ranges, and Quicksort is a general-purpose algorithm with fast average performance. Each algorithm has distinct characteristics regarding comparisons, swaps, and handling large datasets.

Uploaded by

Anh Khoa
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
6 views1 page

Sort Algorithm

The document compares various sorting algorithms: Merge Sort, Radix Sort, and Quicksort, detailing their time and space complexities, stability, in-place status, and best use cases. Merge Sort is stable and efficient for small datasets, while Radix Sort excels with limited digit ranges, and Quicksort is a general-purpose algorithm with fast average performance. Each algorithm has distinct characteristics regarding comparisons, swaps, and handling large datasets.

Uploaded by

Anh Khoa
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 1

Insertion Selectio

Factor Merge Sort Radix Sort Quicksort


Sort n Sort

Best: O(n) All Best/Avg/ Best/Avg/ Best/Avg:


Time
Avg/Worst: cases: Worst: O(n Worst: O(d·n) O(n log n)
Complexity
O(n²) O(n²) log n) (d = # digits) Worst: O(n²)

O(n + k) (k = O(log n)
Space O(n) (due to
O(1) O(1) range of (stack
Complexity merging)
digits) recursion)

No Efficient
Efficient for comparisons (good pivot
Compariso Always Many
small/ordere (non- = fewer
ns O(n²/2) comparisons
dn comparative comparisons
sort) )

Shifts Exactly Moves entire


Swaps/ Bucketing (no Swaps via
elements (n - 1) halves when
Moves swaps) partitioning
(few swaps) swaps merging

❌ No (unless
Stable? ✅ Yes ❌ No ✅ Yes ✅ Yes
modified)

❌ No (uses
In-Place? ✅ Yes ✅ Yes extra ❌ No ✅ Yes
memory)

Very General-
Large
Nearly small Large data purpose,
Best Use datasets
sorted or data, with limited fast average
Case requiring
small arrays simple digit range performanc
stability
logic e

❌ Very ✅ If digit ✅ Great if


Handles ❌ Slow for ✅ Excellent
slow for range is not pivot is
Large n? large n choice
large n too large chosen well

Handles
✅ Few ❌ Many ✅ No swaps at ❌ Can be
Expensive ✅ Moderate
swaps swaps all costly
Swaps?

You might also like