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
Merge SortSorting | Quick SortSorting | |
|---|---|---|
| Use case | Stable, guaranteed O(n log n) sorting; linked lists; external sorting; counting inversions. | General-purpose in-memory array sorting; also the basis of quickselect. |
| Requirements | Extra buffer of size n (arrays) or just pointer rewiring (lists). | Random access; a good pivot strategy (random or median-of-three). |
| Time complexity | Best, average and worst O(n log n). | Average O(n log n); worst O(n^2) with bad pivots. |
| Space complexity | O(n) auxiliary for arrays, O(log n) recursion depth. | O(log n) expected stack space, in place. |
| Strengths | Stable; predictable; parallelizes cleanly; the merge step solves inversion counting and k-way problems. | Fastest in practice due to cache locality and small constants; in place. |
| Weaknesses | Extra memory and more data movement than quick sort; slower constant factors on arrays. | Not stable; worst case quadratic on adversarial or already-sorted input without randomization. |
| Example problems | Merge k sorted lists, count inversions, sort a linked list. | Sort colors (3-way partition), kth largest element (quickselect), top-k via partitioning. |
| Choose this when | Choose merge sort when stability or a worst-case guarantee matters, when sorting linked lists, or when the merge step itself is the solution. | Choose quick sort for fast in-place sorting of arrays where average-case speed matters more than the worst case. |