Comparison Mode
Side-by-side: use case, requirements, complexity, strengths, weaknesses, example problems, and a clear “choose this when…”.
BFS vs DFSDijkstra vs Bellman-FordKruskal vs PrimMerge Sort vs Quick SortHeap vs Priority QueueHash Map vs Tree MapBFS vs DijkstraSliding Window vs Two PointersPrefix Sum vs Segment TreeGreedy vs Dynamic ProgrammingMemoization vs TabulationTarjan vs KosarajuSegment Tree vs Fenwick TreeArray vs Linked ListStack vs QueueQuick Sort vs Heap SortKMP vs Rabin-KarpUnion-Find vs DFSTrie vs Hash MapAVL Tree vs Red-Black Tree
Quick SortSorting | Heap SortSorting | |
|---|---|---|
| Use case | General in-memory sorting with the best average speed. | Sorting with a guaranteed bound and O(1) extra space; partial sorting (top k). |
| Requirements | Random access and a good pivot strategy. | An array that can be heapified in place. |
| Time complexity | Average O(n log n), worst O(n^2). | Best, average, worst O(n log n). |
| Space complexity | O(log n) expected stack. | O(1) auxiliary, iterative. |
| Strengths | Fastest in practice; cache friendly; partition step reusable for quickselect. | Worst-case guarantee; in place; stop early after k extractions for top-k. |
| Weaknesses | Quadratic worst case; not stable; recursive. | Poor cache locality makes it 2-3x slower than quick sort; not stable. |
| Example problems | Sort colors, kth largest element, sort an array. | Kth largest element, top k frequent elements, sort an array under strict memory limits. |
| Choose this when | Choose quick sort (randomized) for raw speed when an occasional bad case is acceptable. | Choose heap sort when you need a hard O(n log n) guarantee with constant extra memory, or only the k largest elements. |