beingsde
Sign In
Back to all DSA patterns
Divide & Conquer•Pattern: Divide & Conquer•Medium

Merge sort — divide and conquer sort

Problem Intuition & Objective

Sort an array using the merge-sort divide-and-conquer technique.

Time ComplexityO(n log n)
Optimal
Space ComplexityO(n)
Memory Bounds
Optimal Algorithmic Approach

Recursive halving + linear merge.

Core Invariants & Edge Cases

  • Divide array in half recursively until size 1
  • Merge two sorted halves in linear time
  • Stable sort; O(n log n) guaranteed
Previous ProblemPacific Atlantic water flowNext Problem QuickSelect — find Kth smallest element in O(n) average

System Design & Architecture Roadmap

Coding interviews are only 50% of the bar. Master High-Level Design, distributed systems, and Object-Oriented LLD.

60+ HLD QuestionsSharding, caching, and real-time distributed systems.27 LLD BlueprintsObject-oriented design patterns with class diagrams.SDE Quick ReferenceLatency numbers and database selection matrix.