Description
Divide-and-conquer sorting. If array length ≤ 1, return (base case). Otherwise split into left and right halves. Recursively merge-sort left and right. Merge the two sorted halves by comparing fronts and appending smaller. Stable. Time O(n log n) always; space O(n) auxiliary.
Source: Wikipedia
Algorithm Flowchart
graph TD
A1["Array A n elements"]
D1{"Base case?\nn le 1"}
B1["Split A into left and right halves"]
C1["MergeSort left\nMergeSort right"]
C2["Merge sorted left and right\ncompare fronts append smaller"]
F1["Return sorted array"]
A1 --> D1
D1 -->|Yes| F1
D1 -->|No| B1
B1 --> C1
C1 --> C2
C2 --> F1
classDef red fill:#ff6b6b,color:#fff,stroke:#c0392b
classDef yellow fill:#ffd43b,color:#000,stroke:#f59f00
classDef green fill:#51cf66,color:#fff,stroke:#40c057
classDef lightblue fill:#74c0fc,color:#fff,stroke:#4dabf7
classDef violet fill:#b197fc,color:#fff,stroke:#9775fa
classDef lavender fill:#e6e6fa,color:#333,stroke:#b19cd9
class A1 red
class B1 yellow
class C1,C2 green
class F1 violet
class D1 lavender
Color Scheme (GLMP 6-Color)
Red
Triggers & Inputs
Triggers & Inputs
Yellow
Structures & Objects
Structures & Objects
Green
Processing & Operations
Processing & Operations
Light Blue
Intermediates & States
Intermediates & States
Violet
Products & Outputs
Products & Outputs
Lavender
Decision diamonds
Decision diamonds
Process Statistics
- Nodes: 6
- Edges: 6
- OR gates: 1
- Loops: 0
- AND gates: 1
- Complexity: O(n log n)
Keywords
- merge sort
- divide and conquer
- sorting
- stable sort