-
Notifications
You must be signed in to change notification settings - Fork 16
/
merge.theory.txt
26 lines (19 loc) · 2.17 KB
/
merge.theory.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
MERGE
GOAL ==> #Concatenating several sorted arrays into a single sorted array.
#Keeps duplicates.
K-WAY MERGE ==> #When merging k several arrays
ITERATIVE MERGE ==> #Concatenate arrays then apply a merge sort
#Time complexity: O(n * log n)
#Space complexity: O(n)
#Can be distributed
DIRECT MERGE ==> #Extract highest value among all k arrays, then iterate
#Time complexity: O(n*k)
#Space complexity: O(n)
# - O(1) when using linked lists
#Variants if high k:
# - store lists heads into a heap or a tournament tree (like tournament sorts),
# making it O(n * log k)
# - divide and conquer, merging two arrays at a time
#2-way merge is called "binary merge".