Merge sort algorithm

Definition

Merge sort is an efficient sorting algorithm that works by dividing an array or list into two halves, recursively sorting each half separately, and then merging them back together in sorted order.

Related terms

Divide-and-Conquer: A problem-solving technique where a problem is divided into smaller subproblems that can be solved independently. Merge sort uses this technique.

Time Complexity: The amount of time taken by an algorithm to run as a function of input size. Merge sort has an average and worst-case time complexity of O(n log n), where n is the number of elements to be sorted.

Stability: A property of a sorting algorithm that preserves the relative order of equal elements. Merge sort is stable, meaning it maintains the original order of equal elements in the input.