Merge Sort (EN)

Merge Sort Algorithm

Merge Sort is an efficient, comparison-based sorting algorithm based on the divide-and-conquer principle that achieves a time complexity of O(n log n). The algorithm repeatedly divides the input sequence into two halves until only individual elements remain, then combines them back in sorted order. Merge Sort is a stable sorting algorithm particularly suited for large datasets as its performance does not depend on the initial order of the data. Due to its guaranteed O(n log n) complexity, it is a preferred choice for applications where predictable performance is important.

Data Flow

flowchart TD     A[Input Array] --> B[Divide]     B --> C[Left Subarray]     B --> D[Right Subarray]     C --> E[Recursively Divide]     D --> E     E --> F[Sort]     F --> G[Merge]     G --> H[Sorted Array] 

In Context

• Typically used together with Quick Sort, Heap Sort
• Related to: Divide-and-conquer principle, Recursion, Sorting algorithms
• Example use case: External sorting of large datasets that do not fit completely into memory