Merge sort
E459515
Merge sort is a comparison-based, divide-and-conquer sorting algorithm that recursively splits a list into halves, sorts them, and then merges the sorted halves into a fully ordered sequence.
Statements (46)
| Predicate | Object |
|---|---|
| instanceOf |
comparison-based algorithm
ⓘ
divide-and-conquer algorithm ⓘ sorting algorithm ⓘ |
| bestSuitedFor |
data that does not fit in memory
ⓘ
sequential access media ⓘ |
| canBeImplementedAs |
bottom-up merge sort
ⓘ
top-down merge sort ⓘ |
| category |
comparison sort
ⓘ
divide-and-conquer sort ⓘ |
| dividesInto | two halves ⓘ |
| ensures | globally sorted order after final merge ⓘ |
| goal | produce fully ordered sequence ⓘ |
| hasAdvantage |
good cache performance in some implementations
ⓘ
predictable O(n log n) running time ⓘ |
| hasDisadvantage |
more overhead than simple quadratic sorts on small n
ⓘ
requires extra memory ⓘ |
| hasProperty |
deterministic
ⓘ
not in-place in standard implementation ⓘ stable ordering of equal elements ⓘ |
| hasStep |
combine step
ⓘ
conquer step ⓘ divide step ⓘ |
| isAdaptive | false ⓘ |
| isComparisonSort | true ⓘ |
| isStable | true ⓘ |
| keyOperation |
comparison
ⓘ
merge ⓘ |
| operatesOn |
array
ⓘ
list ⓘ sequence ⓘ |
| originatedFrom | John von Neumann NERFINISHED ⓘ |
| recursivelySorts |
subarrays
ⓘ
sublists ⓘ |
| requires | auxiliary array for merging ⓘ |
| spaceComplexityInPlaceVariants | O(1) ⓘ |
| spaceComplexityTypical | O(n) ⓘ |
| thenMerges | sorted halves ⓘ |
| timeComplexityBestCase | O(n log n) ⓘ |
| usedIn |
Java Arrays.sort for objects
ⓘ
TimSort as a component idea ⓘ standard library sort implementations ⓘ |
| usesParadigm | divide and conquer ⓘ |
| worksWellFor |
external sorting
ⓘ
large datasets ⓘ linked lists ⓘ |
| yearIntroduced | 1945 ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.