Sorting Algorithms (PDF)

1 Algorithms and Data Structures Winter Term 2024/25 2nd Lecture Sorting by other means Prof. Dr. Matthias Mnich Institute for Algorithms and Complexity ...

1 Algorithms and Data Structures Winter Term 2024/25 2nd Lecture Sorting by other means Prof. Dr. Matthias Mnich Institute for Algorithms and Complexity  2-1 Divide and Conquer ∗ ) Illustrations from [Corman et al. Introduction to Algorithms“, MIT Press] ”  2-2 Divide and Conquer Idea: Divide the card stack into two roughly equal-sized parts. Sort the parts, e.g. with multiple people. Combine the parts into a sorted stack. ∗ ) Illustrations from [Corman et al. Introduction to Algorithms“, MIT Press] ”  2-3 Divide and Conquer Idea: Divide the card stack into two roughly equal-sized parts. Sort the parts, e.g. with multiple people. Combine the parts into a sorted stack. Generally: ∗ ) Illustrations from [Corman et al. Introduction to Algorithms“, MIT Press] ”  2-4 Divide and Conquer Idea: Divide the card stack into two roughly equal-sized parts. Sort the parts, e.g. with multiple people. Combine the parts into a sorted stack. Generally: Divide... ∗ ) Illustrations from [Corman et al. Introduction to Algorithms“, MIT Press] ”  2-5 Divide and Conquer Idea: Divide the card stack into two roughly equal-sized parts. Sort the parts, e.g. with multiple people. Combine the parts into a sorted stack. Generally: Divide... an instance into smaller instances of the same problem. ∗ ) Illustrations from [Corman et al. Introduction to Algorithms“, MIT Press] ”  2-6 Divide and Conquer Idea: Divide the card stack into two roughly equal-sized parts. Sort the parts, e.g. with multiple people. Combine the parts into a sorted stack. Generally: Divide... an instance into smaller instances of the same problem. Conquer... ∗ ) Illustrations from [Corman et al. Introduction to Algorithms“, MIT Press] ”  2-7 Divide and Conquer Idea: Divide the card stack into two roughly equal-sized parts. Sort the parts, e.g. with multiple people. Combine the parts into a sorted stack. Generally: Divide... an instance into smaller instances of the same problem. Conquer... by recursively solving sub-instances – only solve very small instances directly. ∗ ) Illustrations from [Corman et al. Introduction to Algorithms“, MIT Press] ”  2-8 Divide and Conquer Idea: Divide the card stack into two roughly equal-sized parts. Sort the parts, e.g. with multiple people. Combine the parts into a sorted stack. Generally: Divide... an instance into smaller instances of the same problem. Conquer... by recursively solving sub-instances – only solve very small instances directly. ∗ ) Illustrations from [Corman et al. Introduction to Algorithms“, MIT Press] ”  2-9 Divide and Conquer Idea: Divide the card stack into two roughly equal-sized parts. Sort the parts, e.g. with multiple people. Combine the parts into a sorted stack. Generally: Divide... an instance into smaller instances of the same problem. a function which calls itself Conquer... by recursively solving sub-instances – only solve very small instances directly. ∗ ) Illustrations from [Corman et al. Introduction to Algorithms“, MIT Press] ”  2-1 Divide and Conquer Idea: Divide the card stack into two roughly equal-sized parts. Sort the parts, e.g. with multiple people. Combine the parts into a sorted stack. Generally: Divide... an instance into smaller instances of the same problem. a function which calls itself Conquer... by recursively solving sub-instances – only solve very small instances directly. Combine... ∗ ) Illustrations from [Corman et al. Introduction to Algorithms“, MIT Press] ”  2-1 Divide and Conquer Idea: Divide the card stack into two roughly equal-sized parts. Sort the parts, e.g. with multiple people. Combine the parts into a sorted stack. Generally: Divide... an instance into smaller instances of the same problem. a function which calls itself Conquer... by recursively solving sub-instances – only solve very small instances directly. Combine... the partial solutions into a solution of the original ∗instance. ) Illustrations from [Corman et al. Introduction to Algorithms“, MIT Press] ”  2-1 Divide and Conquer MergeSort(int[ ] A, int ℓ = 1, int r = A.length) if ℓ < r then m = ⌊(ℓ + r )/2⌋ MergeSort(A, ℓ, m) MergeSort(A, m + 1, r ) Merge(A, ℓ, m, r ) Generally: Divide... an instance into smaller instances of the same problem. Conquer... by recursively solving sub-instances – only solve very small instances directly. Combine... the partial solutions into a solution of the original ∗instance. ) Illustrations from [Corman et al. Introduction to Algorithms“, MIT Press] ”  2-1 Divide and Conquer MergeSort(int[ ] A, int ℓ = 1, int r = A.length) if ℓ < r then m = ⌊(ℓ + r )/2⌋ default values – MergeSort(A, ℓ, m) MergeSort(A, m + 1, r ) Merge(A, ℓ, m, r ) Generally: Divide... an instance into smaller instances of the same problem. Conquer... by recursively solving sub-instances – only solve very small instances directly. Combine... the partial solutions into a solution of the original ∗instance. ) Illustrations from [Corman et al. Introduction to Algorithms“, MIT Press] ”  2-1 Divide and Conquer MergeSort(int[ ] A, int ℓ = 1, int r = A.length) if ℓ < r then m = ⌊(ℓ + r )/2⌋ default values – MergeSort(A, ℓ, m) Through this, the function MergeSort(A, m + 1, r ) MergeSort(A) ≡ Merge(A, ℓ, m, r ) MergeSort(A, 1, A.length) is defined. Generally: Divide... an instance into smaller instances of the same problem. Conquer... by recursively solving sub-instances – only solve very small instances directly. Combine... the partial solutions into a solution of the original ∗instance. ) Illustrations from [Corman et al. Introduction to Algorithms“, MIT Press] ”  2-1 Divide and Conquer MergeSort(int[ ] A, int ℓ = 1, int r = A.length) if ℓ < r then m = ⌊(ℓ + r )/2⌋ MergeSort(A, ℓ, m) MergeSort(A, m + 1, r ) Merge(A, ℓ, m, r ) Generally: Divide... an instance into smaller instances of the same problem. Conquer... by recursively solving sub-instances – only solve very small instances directly. Combine... the partial solutions into a solution of the original ∗instance. ) Illustrations from [Corman et al. Introduction to Algorithms“, MIT Press] ”  2-1 Divide and Conquer MergeSort(int[ ] A, int ℓ = 1, int r = A.length) if ℓ < r then m = ⌊(ℓ + r )/2⌋ MergeSort(A, ℓ, m) MergeSort(A, m + 1, r ) Merge(A, ℓ, m, r ) Generally: Divide... an instance into smaller instances of the same problem. Conquer... by recursively solving sub-instances – only solve very small instances directly. Combine... the partial solutions into a solution of the original ∗instance. ) Illustrations from [Corman et al. Introduction to Algorithms“, MIT Press] ”  2-1 Divide and Conquer MergeSort(int[ ] A, int ℓ = 1, int r = A.length) if ℓ < r then m = ⌊(ℓ + r )/2⌋ MergeSort(A, ℓ, m) MergeSort(A, m + 1, r ) Merge(A, ℓ, m, r ) Generally: Divide... an instance into smaller instances of the same problem. Conquer... by recursively solving sub-instances – only solve very small instances directly. Combine... the partial solutions into a solution of the original ∗instance. ) Illustrations from [Corman et al. Introduction to Algorithms“, MIT Press] ”  2-1 Divide and Conquer MergeSort(int[ ] A, int ℓ = 1, int r = A.length) if ℓ < r then m = ⌊(ℓ + r )/2⌋ } divide MergeSort(A, ℓ, m) MergeSort(A, m + 1, r ) Merge(A, ℓ, m, r ) Generally: Divide... an instance into smaller instances of the same problem. Conquer... by recursively solving sub-instances – only solve very small instances directly. Combine... the partial solutions into a solution of the original ∗instance. ) Illustrations from [Corman et al. Introduction to Algorithms“, MIT Press] ”  2-1 Divide and Conquer MergeSort(int[ ] A, int ℓ = 1, int r = A.length) if ℓ < r then m = ⌊(ℓ + r )/2⌋ } divide MergeSort(A, ℓ, m) MergeSort(A, m + 1, r ) Merge(A, ℓ, m, r ) Generally: Divide... an instance into smaller instances of the same problem. Conquer... by recursively solving sub-instances – only solve very small instances directly. Combine... the partial solutions into a solution of the original ∗instance. ) Illustrations from [Corman et al. Introduction to Algorithms“, MIT Press] ”  2-2 Divide and Conquer MergeSort(int[ ] A, int ℓ = 1, int r = A.length) if ℓ < r then m = ⌊(ℓ + r )/2⌋ } divide MergeSort(A, ℓ, m) MergeSort(A, m + 1, r ) } conquer Merge(A, ℓ, m, r ) Generally: Divide... an instance into smaller instances of the same problem. Conquer... by recursively solving sub-instances – only solve very small instances directly. Combine... the partial solutions into a solution of the original ∗instance. ) Illustrations from [Corman et al. Introduction to Algorithms“, MIT Press] ”  2-2 Divide and Conquer MergeSort(int[ ] A, int ℓ = 1, int r = A.length) if ℓ < r then m = ⌊(ℓ + r )/2⌋ } divide MergeSort(A, ℓ, m) MergeSort(A, m + 1, r ) } conquer Merge(A, ℓ, m, r ) Generally: Divide... an instance into smaller instances of the same problem. Conquer... by recursively solving sub-instances – only solve very small instances directly. Combine... the partial solutions into a solution of the original ∗instance. ) Illustrations from [Corman et al. Introduction to Algorithms“, MIT Press] ”  2-2 Divide and Conquer MergeSort(int[ ] A, int ℓ = 1, int r = A.length) if ℓ < r then m = ⌊(ℓ + r )/2⌋ } divide MergeSort(A, ℓ, m) MergeSort(A, m + 1, r ) } conquer Merge(A, ℓ, m, r ) } combine Generally: Divide... an instance into smaller instances of the same problem. Conquer... by recursively solving sub-instances – only solve very small instances directly. Combine... the partial solutions into a solution of the original ∗instance. ) Illustrations from [Corman et al. Introduction to Algorithms“, MIT Press] ”  2-2 Divide and Conquer MergeSort(int[ ] A, int ℓ = 1, int r = A.length) if ℓ < r then m = ⌊(ℓ + r )/2⌋ } divide MergeSort(A, ℓ, m) MergeSort(A, m + 1, r ) } conquer Merge(A, ℓ, m, r ) } combine Generally: Divide... an instance into smaller instances of the same problem. Conquer... by recursively solving sub-instances – only solve very small instances directly. Combine... the partial solutions into a solution of the original ∗instance. ) Illustrations from [Corman et al. Introduction to Algorithms“, MIT Press] ”  2-2 Divide and Conquer MergeSort(int[ ] A, int ℓ = 1, int r = A.length) if ℓ < r then m = ⌊(ℓ + r )/2⌋ } divide MergeSort(A, ℓ, m) MergeSort(A, m + 1, r ) } conquer Merge(A, ℓ, m, r ) } combine To do! Generally: Divide... an instance into smaller instances of the same problem. Conquer... by recursively solving sub-instances – only solve very small instances directly. Combine... the partial solutions into a solution of the original ∗instance. ) Illustrations from [Corman et al. Introduction to Algorithms“, MIT Press] ”  3-1 Combine  3-2 Combine Merge(int[ ] A, int ℓ, int m, int r )  3-3 Combine Merge(int[ ] A, int ℓ, int m, int r ) A ℓ m r  3-4 Combine Merge(int[ ] A, int ℓ, int m, int r ) n1 = m − ℓ + 1; n2 = r − m L = new int[1..n1 + 1]; R = new int[1..n2 + 1] L[1..n1 ] = A[ℓ..m] R[1..n2 ] = A[m + 1..r ] L[n1 + 1] = R[n2 + 1] = ∞ i =j =1 for k = ℓ to r do if L[i] ≤ R[j] then A[k] = L[i] i =i +1 else A[k] = R[j] A j =j +1 ℓ m r  3-5 Combine Merge(int[ ] A, int ℓ, int m, int r ) n1 = m − ℓ + 1; n2 = r − m L = new int[1..n1 + 1]; R = new int[1..n2 + 1] L[1..n1 ] = A[ℓ..m] R[1..n2 ] = A[m + 1..r ] L[n1 + 1] = R[n2 + 1] = ∞ i =j =1 for k = ℓ to r do if L[i] ≤ R[j] then A[k] = L[i] i =i +1 n1 n2 else z}|{ z}|{ A[k] = R[j] A j =j +1 ℓ m r  3-6 Combine Merge(int[ ] A, int ℓ, int m, int r ) n1 = m − ℓ + 1; n2 = r − m L = new int[1..n1 + 1]; R = new int[1..n2 + 1] L[1..n1 ] = A[ℓ..m] R[1..n2 ] = A[m + 1..r ] L[n1 + 1] = R[n2 + 1] = ∞ i =j =1 for k = ℓ to r do if L[i] ≤ R[j] then A[k] = L[i] i =i +1 n1 n2 else z}|{ z}|{ A[k] = R[j] A j =j +1 ℓ m r  3-7 Combine Merge(int[ ] A, int ℓ, int m, int r ) n1 = m − ℓ + 1; n2 = r − m L = new int[1..n1 + 1]; R = new int[1..n2 + 1] L[1..n1 ] = A[ℓ..m] R[1..n2 ] = A[m + 1..r ] L[n1 + 1] = R[n2 + 1] = ∞ i =j =1 for k = ℓ to r do if L[i] ≤ R[j] then A[k] = L[i] i =i +1 n1 n2 else z}|{ z}|{ A[k] = R[j] A j =j +1 ℓ m r  3-8 Combine Merge(int[ ] A, int ℓ, int m, int r ) n1 = m − ℓ + 1; n2 = r − m L = new int[1..n1 + 1]; R = new int[1..n2 + 1] L[1..n1 ] = A[ℓ..m] R[1..n2 ] = A[m + 1..r ] L[n1 + 1] = R[n2 + 1] = ∞ i =j =1 for k = ℓ to r do if L[i] ≤ R[j] then A[k] = L[i] i =i +1 n1 n2 else z}|{ z}|{ A[k] = R[j] A j =j +1 ℓ m r  3-9 Combine Merge(int[ ] A, int ℓ, int m, int r ) n1 = m − ℓ + 1; n2 = r − m L = new int[1..n1 + 1]; R = new int[1..n2 + 1] L[1..n1 ] = A[ℓ..m] R[1..n2 ] = A[m + 1..r ] L[n1 + 1] = R[n2 + 1] = ∞ i =j =1 for k = ℓ to r do if L[i] ≤ R[j] then L A[k] = L[i] i =i +1 n1 n2 else z}|{ z}|{ A[k] = R[j] A j =j +1 ℓ m r  3-1 Combine Merge(int[ ] A, int ℓ, int m, int r ) n1 = m − ℓ + 1; n2 = r − m L = new int[1..n1 + 1]; R = new int[1..n2 + 1] L[1..n1 ] = A[ℓ..m] R[1..n2 ] = A[m + 1..r ] for i = 1 to n1 do L[n1 + 1] = R[n2 + 1] = ∞ L[i ] = A[(ℓ − 1) + i ] i =j =1 for k = ℓ to r do if L[i] ≤ R[j] then L A[k] = L[i] i =i +1 n1 n2 else z}|{ z}|{ A[k] = R[j] A j =j +1 ℓ m r  3-1 Combine Merge(int[ ] A, int ℓ, int m, int r ) n1 = m − ℓ + 1; n2 = r − m L = new int[1..n1 + 1]; R = new int[1..n2 + 1] L[1..n1 ] = A[ℓ..m] R[1..n2 ] = A[m + 1..r ] for i = 1 to n1 do L[n1 + 1] = R[n2 + 1] = ∞ L[i ] = A[(ℓ − 1) + i ] i =j =1 for k = ℓ to r do if L[i] ≤ R[j] then L A[k] = L[i] i =i +1 n1 n2 else z}|{ z}|{ A[k] = R[j] A j =j +1 ℓ m r  3-1 Combine Merge(int[ ] A, int ℓ, int m, int r ) n1 = m − ℓ + 1; n2 = r − m L = new int[1..n1 + 1]; R = new int[1..n2 + 1] L[1..n1 ] = A[ℓ..m] R[1..n2 ] = A[m + 1..r ] L[n1 + 1] = R[n2 + 1] = ∞ i =j =1 R for k = ℓ to r do if L[i] ≤ R[j] then L A[k] = L[i] i =i +1 n1 n2 else z}|{ z}|{ A[k] = R[j] A j =j +1 ℓ m r  3-1 Combine Merge(int[ ] A, int ℓ, int m, int r ) n1 = m − ℓ + 1; n2 = r − m L = new int[1..n1 + 1]; R = new int[1..n2 + 1] L[1..n1 ] = A[ℓ..m] R[1..n2 ] = A[m + 1..r ] L[n1 + 1] = R[n2 + 1] = ∞ i =j =1 R for k = ℓ to r do if L[i] ≤ R[j] then L A[k] = L[i] i =i +1 n1 n2 else z}|{ z}|{ A[k] = R[j] A j =j +1 ℓ m r  3-1 Combine Merge(int[ ] A, int ℓ, int m, int r ) n1 = m − ℓ + 1; n2 = r − m L = new int[1..n1 + 1]; R = new int[1..n2 + 1] L[1..n1 ] = A[ℓ..m] R[1..n2 ] = A[m + 1..r ] L[n1 + 1] = R[n2 + 1] = ∞ i =j =1 R ∞ for k = ℓ to r do if L[i] ≤ R[j] then L ∞ A[k] = L[i] i =i +1 n1 n2 else z}|{ z}|{ A[k] = R[j] A j =j +1 ℓ m r  3-1 Combine Merge(int[ ] A, int ℓ, int m, int r ) n1 = m − ℓ + 1; n2 = r − m L = new int[1..n1 + 1]; R = new int[1..n2 + 1] L[1..n1 ] = A[ℓ..m] R[1..n2 ] = A[m + 1..r ] sentinel (ger. Stopper ) L[n1 + 1] = R[n2 + 1] = ∞ i =j =1 R ∞ for k = ℓ to r do if L[i] ≤ R[j] then L ∞ A[k] = L[i] i =i +1 n1 n2 else z}|{ z}|{ A[k] = R[j] A j =j +1 ℓ m r  3-1 Combine Merge(int[ ] A, int ℓ, int m, int r ) n1 = m − ℓ + 1; n2 = r − m L = new int[1..n1 + 1]; R = new int[1..n2 + 1] L[1..n1 ] = A[ℓ..m] R[1..n2 ] = A[m + 1..r ] j L[n1 + 1] = R[n2 + 1] = ∞ i =j =1 R ∞ i for k = ℓ to r do if L[i] ≤ R[j] then L ∞ A[k] = L[i] i =i +1 n1 n2 else z}|{ z}|{ A[k] = R[j] A j =j +1 k ℓ m r  3-1 Combine Merge(int[ ] A, int ℓ, int m, int r ) n1 = m − ℓ + 1; n2 = r − m L = new int[1..n1 + 1]; R = new int[1..n2 + 1] L[1..n1 ] = A[ℓ..m] R[1..n2 ] = A[m + 1..r ] j L[n1 + 1] = R[n2 + 1] = ∞ i =j =1 R ∞ i for k = ℓ to r do if L[i] ≤ R[j] then L ∞ Challenge: A[k] = L[i] Close i = iyour + 1 books and your browser! n1 n2 else Write the rest of the routine with your neighbor! z}|{ z}|{ A[k] = R[j] A Use the two new arrays L and R for this. j =j +1 k You have 5 minutes. ℓ m r  3-1 Combine Merge(int[ ] A, int ℓ, int m, int r ) n1 = m − ℓ + 1; n2 = r − m L = new int[1..n1 + 1]; R = new int[1..n2 + 1] L[1..n1 ] = A[ℓ..m] R[1..n2 ] = A[m + 1..r ] j L[n1 + 1] = R[n2 + 1] = ∞ i =j =1 R ∞ i for k = ℓ to r do if L[i] ≤ R[j] then L ∞ A[k] = L[i] i =i +1 n1 n2 else z}|{ z}|{ A[k] = R[j] A j =j +1 k ℓ m r  3-1 Combine Merge(int[ ] A, int ℓ, int m, int r ) n1 = m − ℓ + 1; n2 = r − m L = new int[1..n1 + 1]; R = new int[1..n2 + 1] L[1..n1 ] = A[ℓ..m] R[1..n2 ] = A[m + 1..r ] j L[n1 + 1] = R[n2 + 1] = ∞ i =j =1 R ∞ i for k = ℓ to r do if L[i] ≤ R[j] then L ∞ A[k] = L[i] i =i +1 n1 n2 else z}|{ z}|{ A[k] = R[j] A j =j +1 k ℓ m r  3-2 Combine Merge(int[ ] A, int ℓ, int m, int r ) n1 = m − ℓ + 1; n2 = r − m L = new int[1..n1 + 1]; R = new int[1..n2 + 1] L[1..n1 ] = A[ℓ..m] R[1..n2 ] = A[m + 1..r ] j L[n1 + 1] = R[n2 + 1] = ∞ i =j =1 R ∞ i for k = ℓ to r do if L[i] ≤ R[j] then L ∞ A[k] = L[i] i =i +1 n1 n2 else z}|{ z}|{ A[k] = R[j] A j =j +1 k ℓ m r  3-2 Combine Merge(int[ ] A, int ℓ, int m, int r ) n1 = m − ℓ + 1; n2 = r − m L = new int[1..n1 + 1]; R = new int[1..n2 + 1] L[1..n1 ] = A[ℓ..m] R[1..n2 ] = A[m + 1..r ] j L[n1 + 1] = R[n2 + 1] = ∞ i =j =1 R ∞ i for k = ℓ to r do if L[i] ≤ R[j] then L ∞ A[k] = L[i] i =i +1 n1 n2 else z}|{ z}|{ A[k] = R[j] A j =j +1 ℓ k m r  3-2 Combine Merge(int[ ] A, int ℓ, int m, int r ) n1 = m − ℓ + 1; n2 = r − m L = new int[1..n1 + 1]; R = new int[1..n2 + 1] L[1..n1 ] = A[ℓ..m] R[1..n2 ] = A[m + 1..r ] j L[n1 + 1] = R[n2 + 1] = ∞ i =j =1 R ∞ i for k = ℓ to r do if L[i] ≤ R[j] then L ∞ A[k] = L[i] i =i +1 n1 n2 else z}|{ z}|{ A[k] = R[j] A j =j +1 ℓ k m r  3-2 Combine Merge(int[ ] A, int ℓ, int m, int r ) n1 = m − ℓ + 1; n2 = r − m L = new int[1..n1 + 1]; R = new int[1..n2 + 1] L[1..n1 ] = A[ℓ..m] R[1..n2 ] = A[m + 1..r ] j L[n1 + 1] = R[n2 + 1] = ∞ i =j =1 R ∞ i for k = ℓ to r do if L[i] ≤ R[j] then L ∞ A[k] = L[i] i =i +1 n1 n2 else z}|{ z}|{ A[k] = R[j] A j =j +1 ℓ k m r  3-2 Combine Merge(int[ ] A, int ℓ, int m, int r ) n1 = m − ℓ + 1; n2 = r − m L = new int[1..n1 + 1]; R = new int[1..n2 + 1] L[1..n1 ] = A[ℓ..m] R[1..n2 ] = A[m + 1..r ] j L[n1 + 1] = R[n2 + 1] = ∞ i =j =1 R ∞ i for k = ℓ to r do if L[i] ≤ R[j] then L ∞ A[k] = L[i] i =i +1 n1 n2 else z}|{ z}|{ A[k] = R[j] A j =j +1 ℓ k m r  3-2 Combine Merge(int[ ] A, int ℓ, int m, int r ) n1 = m − ℓ + 1; n2 = r − m L = new int[1..n1 + 1]; R = new int[1..n2 + 1] L[1..n1 ] = A[ℓ..m] R[1..n2 ] = A[m + 1..r ] j L[n1 + 1] = R[n2 + 1] = ∞ i =j =1 R ∞ i for k = ℓ to r do if L[i] ≤ R[j] then L ∞ A[k] = L[i] i =i +1 n1 n2 else z}|{ z}|{ A[k] = R[j] A j =j +1 ℓ k m r  3-2 Combine Merge(int[ ] A, int ℓ, int m, int r ) n1 = m − ℓ + 1; n2 = r − m L = new int[1..n1 + 1]; R = new int[1..n2 + 1] L[1..n1 ] = A[ℓ..m] R[1..n2 ] = A[m + 1..r ] j L[n1 + 1] = R[n2 + 1] = ∞ i =j =1 R ∞ i for k = ℓ to r do if L[i] ≤ R[j] then L ∞ A[k] = L[i] i =i +1 n1 n2 else z}|{ z}|{ A[k] = R[j] A j =j +1 ℓ k m r But... is all of this even correct???  4-1 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1] L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 for k = ℓ to r do if L[i ] ≤ R [j ] then A [k ] = L [i ] i =i +1 else A [k ] = R [j ] j =j +1  4-2 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 for k = ℓ to r do if L[i ] ≤ R [j ] then A [k ] = L [i ] i =i +1 else A [k ] = R [j ] j =j +1  4-3 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 for k = ℓ to r do if L[i ] ≤ R [j ] then A [k ] = L [i ] i =i +1 else A [k ] = R [j ] j =j +1  4-4 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 for k = ℓ to r do if L[i ] ≤ R [j ] then A [k ] = L [i ] i =i +1 else A [k ] = R [j ] j =j +1  4-5 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do many smallest elements of if L[i ] ≤ R [j ] then L ∪ R sorted. A [k ] = L [i ] i =i +1 else A [k ] = R [j ] j =j +1  4-6 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do many smallest elements of if L[i ] ≤ R [j ] then L ∪ R sorted. A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R , which have A [k ] = R [j ] not been copied into A yet. j =j +1  4-7 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do many smallest elements of if L[i ] ≤ R [j ] then L ∪ R sorted. A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R , which have A [k ] = R [j ] not been copied into A yet. j =j +1 1. Initialisation  4-8 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do many smallest elements of if L[i ] ≤ R [j ] then L ∪ R sorted. A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R , which have A [k ] = R [j ] not been copied into A yet. j =j +1 1. Initialisation Since on the first loop iteration k = ℓ holds, A[ℓ..k − 1] = ⟨⟩ has the 0 smallest elements of L ∪ R.  4-9 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do many smallest elements of if L[i ] ≤ R [j ] then L ∪ R sorted. A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R , which have A [k ] = R [j ] not been copied into A yet. j =j +1 1. Initialisation Since on the first loop iteration k = ℓ holds, A[ℓ..k − 1] = ⟨⟩ has the 0 smallest elements of L ∪ R. Because i = j = 1 holds, L[i ] and R [j ] are the smallest elements not yet copied.  4-1 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do many smallest elements of if L[i ] ≤ R [j ] then L ∪ R sorted. A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R , which have A [k ] = R [j ] not been copied into A yet. j =j +1 1. Initialisation Since on the first loop iteration k = ℓ holds, A[ℓ..k − 1] = ⟨⟩ has the 0 smallest elements of L ∪ R. Because i = j = 1 holds, L[i ] and R [j ] are the smallest elements not yet copied.  5-1 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R , which have A [k ] = R [j ] not been copied into A yet. j =j +1 1. Initialisation  5-2 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R , which have A [k ] = R [j ] not been copied into A yet. j =j +1 1. Initialisation 2. Maintenance  5-3 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R , which have A [k ] = R [j ] not been copied into A yet. j =j +1 1. Initialisation 2. Maintenance Two cases: (a) L[i ] ≤ R [j ], (b) R [j ] < L[i ].  5-4 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then // Case (a) A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R , which have A [k ] = R [j ] not been copied into A yet. j =j +1 1. Initialisation 2. Maintenance Two cases: (a) L[i ] ≤ R [j ], (b) R [j ] < L[i ]. Consider Case (a).  5-5 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then // Case (a) A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R , which have A [k ] = R [j ] not been copied into A yet. j =j +1 1. Initialisation 2. Maintenance Two cases: (a) L[i ] ≤ R [j ], (b) R [j ] < L[i ]. Consider Case (a). Now holds: (by INV)  5-6 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then // Case (a) A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R , which have A [k ] = R [j ] not been copied into A yet. j =j +1 1. Initialisation 2. Maintenance Two cases: (a) L[i ] ≤ R [j ], (b) R [j ] < L[i ]. Consider Case (a). Now holds: – A[ℓ..k ] contains the smallest k − ℓ + 1 elements sorted. (by INV)  5-7 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then // Case (a) A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R , which have A [k ] = R [j ] not been copied into A yet. j =j +1 1. Initialisation 2. Maintenance Two cases: (a) L[i ] ≤ R [j ], (b) R [j ] < L[i ]. Consider Case (a). Now holds: – A[ℓ..k ] contains the smallest k − ℓ + 1 elements sorted. (by INV) – L[i + 1] is smallest not yet copied element in L.  5-8 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then // Case (a) A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R , which have A [k ] = R [j ] not been copied into A yet. j =j +1 1. Initialisation 2. Maintenance Two cases: (a) L[i ] ≤ R [j ], (b) R [j ] < L[i ]. Consider Case (a). Now holds: – A[ℓ..k ] contains the smallest k − ℓ + 1 elements sorted. (by INV) – L[i + 1] is smallest not yet copied element in L. increase i  5-9 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then // Case (a) A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R , which have A [k ] = R [j ] not been copied into A yet. j =j +1 1. Initialisation 2. Maintenance Two cases: (a) L[i ] ≤ R [j ], (b) R [j ] < L[i ]. Consider Case (a). Now holds: – A[ℓ..k ] contains the smallest k − ℓ + 1 elements sorted. (by INV) – L[i + 1] is smallest not yet copied element in L. increase i ⇒  5-1 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then // Case (a) A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R , which have A [k ] = R [j ] not been copied into A yet. j =j +1 1. Initialisation 2. Maintenance Two cases: (a) L[i ] ≤ R [j ], (b) R [j ] < L[i ]. Consider Case (a). Now holds: – A[ℓ..k ] contains the smallest k − ℓ + 1 elements sorted. (by INV) – L[i + 1] is smallest not yet copied element in L. increase i ⇒ L[i ] is smallest not yet copied element in L.  5-1 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then // Case (a) A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R , which have A [k ] = R [j ] not been copied into A yet. j =j +1 1. Initialisation 2. Maintenance Two cases: (a) L[i ] ≤ R [j ], (b) R [j ] < L[i ]. Consider Case (a). Now holds: – A[ℓ..k ] contains the smallest k − ℓ + 1 elements sorted. (by INV) – L[i + 1] is smallest not yet copied element in L. increase i ⇒ L[i ] is smallest not yet copied element in L. increase k  5-1 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then // Case (a) A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R , which have A [k ] = R [j ] not been copied into A yet. j =j +1 1. Initialisation 2. Maintenance Two cases: (a) L[i ] ≤ R [j ], (b) R [j ] < L[i ]. Consider Case (a). Now holds: – A[ℓ..k ] contains the smallest k − ℓ + 1 elements sorted. (by INV) – L[i + 1] is smallest not yet copied element in L. increase i ⇒ L[i ] is smallest not yet copied element in L. increase k ⇒  5-1 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then // Case (a) A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R , which have A [k ] = R [j ] not been copied into A yet. j =j +1 1. Initialisation 2. Maintenance Two cases: (a) L[i ] ≤ R [j ], (b) R [j ] < L[i ]. Consider Case (a). Now holds: – A[ℓ..k ] contains the smallest k − ℓ + 1 elements sorted. (by INV) – L[i + 1] is smallest not yet copied element in L. increase i ⇒ L[i ] is smallest not yet copied element in L. increase k ⇒ A[ℓ..k − 1] has the k − ℓ smallest elements sorted.  5-1 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then // Case (a) A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R , which have A [k ] = R [j ] not been copied into A yet. j =j +1 1. Initialisation 2. Maintenance Two cases: (a) L[i ] ≤ R [j ], (b) R [j ] < L[i ]. Consider Case (a). Now holds: – A[ℓ..k ] contains the smallest k − ℓ + 1 elements sorted. (by INV) – L[i + 1] is smallest not yet copied element in L. increase i ⇒ L[i ] is smallest not yet copied element in L. ⇒ increase k ⇒ A[ℓ..k − 1] has the k − ℓ smallest elements sorted.  5-1 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then // Case (a) A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R , which have A [k ] = R [j ] not been copied into A yet. j =j +1 1. Initialisation 2. Maintenance Two cases: (a) L[i ] ≤ R [j ], (b) R [j ] < L[i ]. Consider Case (a). Now holds: – A[ℓ..k ] contains the smallest k − ℓ + 1 elements sorted. (by INV) – L[i + 1] is smallest not yet copied element in L. INV! increase i ⇒ L[i ] is smallest not yet copied element in L. ⇒ increase k ⇒ A[ℓ..k − 1] has the k − ℓ smallest elements sorted.  5-1 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then // Case (a) A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R , which have A [k ] = R [j ] not been copied into A yet. j =j +1 1. Initialisation 2. Maintenance Two cases: (a) L[i ] ≤ R [j ], (b) R [j ] < L[i ]. Consider Case (a). Now holds: – A[ℓ..k ] contains the smallest k − ℓ + 1 elements sorted. (by INV) – L[i + 1] is smallest not yet copied element in L. INV! increase i ⇒ L[i ] is smallest not yet copied element in L. ⇒ increase k ⇒ A[ℓ..k − 1] has the k − ℓ smallest elements sorted.  5-1 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then // Case (a) A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else // Case (b) elements in L and R , which have A [k ] = R [j ] not been copied into A yet. j =j +1 1. Initialisation 2. Maintenance Two cases: (a) L[i ] ≤ R [j ], (b) R [j ] < L[i ]. Consider Case (a). Now holds: – A[ℓ..k ] contains the smallest k − ℓ + 1 elements sorted. (by INV) – L[i + 1] is smallest not yet copied element in L. INV! increase i ⇒ L[i ] is smallest not yet copied element in L. ⇒ increase k ⇒ A[ℓ..k − 1] has the k − ℓ smallest elements sorted.  5-1 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then // Case (a) A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else // Case (b) elements in L and R , which have A [k ] = R [j ] not been copied into A yet. j =j +1 1. Initialisation 2. Maintenance (Case (b) symmetric.) Two cases: (a) L[i ] ≤ R [j ], (b) R [j ] < L[i ]. Consider Case (a). Now holds: – A[ℓ..k ] contains the smallest k − ℓ + 1 elements sorted. (by INV) – L[i + 1] is smallest not yet copied element in L. INV! increase i ⇒ L[i ] is smallest not yet copied element in L. ⇒ increase k ⇒ A[ℓ..k − 1] has the k − ℓ smallest elements sorted.  5-1 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then // Case (a) A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else // Case (b) elements in L and R , which have A [k ] = R [j ] not been copied into A yet. j =j +1 1. Initialisation 2. Maintenance (Case (b) symmetric.) Two cases: (a) L[i ] ≤ R [j ], (b) R [j ] < L[i ]. Consider Case (a). Now holds: – A[ℓ..k ] contains the smallest k − ℓ + 1 elements sorted. (by INV) – L[i + 1] is smallest not yet copied element in L. INV! increase i ⇒ L[i ] is smallest not yet copied element in L. ⇒ increase k ⇒ A[ℓ..k − 1] has the k − ℓ smallest elements sorted.  5-2 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then // Case (a) A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else // Case (b) elements in L and R , which have A [k ] = R [j ] not been copied into A yet. j =j +1 1. Initialisation 2. Maintenance (Case (b) symmetric.) Two cases: (a) L[i ] ≤ R [j ], (b) R [j ] < L[i ]. Consider Case (a). Now holds: – A[ℓ..k ] contains the smallest k − ℓ + 1 elements sorted. (by INV) – L[i + 1] is smallest not yet copied element in L. INV! increase i ⇒ L[i ] is smallest not yet copied element in L. ⇒ increase k ⇒ A[ℓ..k − 1] has the k − ℓ smallest elements sorted.  6-1 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R which have not A [k ] = R [j ] been copied into A yet. j =j +1 1. Initialisation 2. Maintenance  6-2 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R which have not A [k ] = R [j ] been copied into A yet. j =j +1 1. Initialisation 2. Maintenance 3. Termination  6-3 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R which have not A [k ] = R [j ] been copied into A yet. j =j +1 1. Initialisation 2. Maintenance 3. Termination After termination of the for loop, k = r + 1.  6-4 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R which have not A [k ] = R [j ] been copied into A yet. j =j +1 1. Initialisation 2. Maintenance 3. Termination After termination of the for loop, k = r + 1. ⇒ A[ℓ..k − 1] = A[ℓ..r ] contains the r − ℓ + 1 smallest elements of L ∪ R sorted.  6-5 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R which have not A [k ] = R [j ] been copied into A yet. j =j +1 1. Initialisation 2. Maintenance 3. Termination After termination of the for loop, k = r + 1. ⇒ A[ℓ..k − 1] = A[ℓ..r ] contains the r − ℓ + 1 smallest elements of L ∪ R sorted. |L ∪ R | = n1 + n2 + 2  6-6 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R which have not A [k ] = R [j ] been copied into A yet. j =j +1 1. Initialisation 2. Maintenance 3. Termination After termination of the for loop, k = r + 1. ⇒ A[ℓ..k − 1] = A[ℓ..r ] contains the r − ℓ + 1 smallest elements of L ∪ R sorted. |L ∪ R | = n1 + n2 + 2 = r − ℓ + 3  6-7 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R which have not A [k ] = R [j ] been copied into A yet. j =j +1 1. Initialisation 2. Maintenance 3. Termination After termination of the for loop, k = r + 1. ⇒ A[ℓ..k − 1] = A[ℓ..r ] contains the r − ℓ + 1 smallest elements of L ∪ R sorted. |L ∪ R | = n1 + n2 + 2 = r − ℓ + 3  6-8 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R which have not A [k ] = R [j ] been copied into A yet. j =j +1 1. Initialisation 2. Maintenance 3. Termination After termination of the for loop, k = r + 1. ⇒ A[ℓ..k − 1] = A[ℓ..r ] contains the r − ℓ + 1 smallest elements of L ∪ R sorted. |L ∪ R | = n1 + n2 + 2 = r − ℓ + 3  6-9 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R which have not A [k ] = R [j ] been copied into A yet. j =j +1 1. Initialisation 2. Maintenance 3. Termination After termination of the for loop, k = r + 1. ⇒ A[ℓ..k − 1] = A[ℓ..r ] contains the r − ℓ + 1 smallest elements of L ∪ R sorted. +2 sentinels |L ∪ R | = n1 + n2 + 2 = r − ℓ + 3  6-1 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R which have not A [k ] = R [j ] been copied into A yet. j =j +1 1. Initialisation 2. Maintenance 3. Termination After termination of the for loop, k = r + 1. ⇒ A[ℓ..k − 1] = A[ℓ..r ] contains the r − ℓ + 1 smallest elements of L ∪ R sorted. +2 sentinels |L ∪ R | = n1 + n2 + 2 = r − ℓ + 3 ⇒ A[ℓ..r ] sorted correctly  6-1 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R which have not A [k ] = R [j ] been copied into A yet. j =j +1 1. Initialisation 2. Maintenance 3. Termination After termination of the for loop, k = r + 1. ⇒ A[ℓ..k − 1] = A[ℓ..r ] contains the r − ℓ + 1 smallest elements of L ∪ R sorted. +2 sentinels |L ∪ R | = n1 + n2 + 2 = r − ℓ + 3 ⇒ A[ℓ..r ] sorted correctly  7-1 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R which have not A [k ] = R [j ] been copied into A yet. j =j +1 1. Initialisation 2. Maintenance 3. Termination  7-2 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R which have not A [k ] = R [j ] been copied into A yet. j =j +1 1. Initialisation 2. Maintenance 3. Termination Therefore, Merge is correct! q.e.d.  7-3 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R which have not A [k ] = R [j ] been copied into A yet. j =j +1 1. Initialisation 2. Maintenance 3. Termination Therefore, Merge is correct! q.e.d. Run time?  7-4 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R which have not A [k ] = R [j ] been copied into A yet. j =j +1 1. Initialisation 2. Maintenance 3. Termination Therefore, Merge is correct! q.e.d. Run time?  7-5 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R which have not A [k ] = R [j ] been copied into A yet. j =j +1 1. Initialisation 2. Maintenance 3. Termination Therefore, Merge is correct! q.e.d. Run time? Merge makes exactly r − ℓ + 1 comparisons⋆.  7-6 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R which have not A [k ] = R [j ] been copied into A yet. j =j +1 1. Initialisation 2. Maintenance 3. Termination Therefore, Merge is correct! q.e.d. Run time? Merge makes exactly r − ℓ + 1 comparisons⋆. And MergeSort?  7-7 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R which have not A [k ] = R [j ] been copied into A yet. j =j +1 1. Initialisation 2. Maintenance 3. Termination Therefore, Merge is correct! q.e.d. Run time? Merge makes exactly r − ℓ + 1 comparisons⋆. And MergeSort? Correct?  7-8 Merge(int[ ] A, int ℓ, int m, int r ) Correctness of Merge n1 = m − ℓ + 1; n2 = r − m create L[1..n1 + 1] and R [1..n2 + 1]... by the template! L[1..n1 ] = A[ℓ..m] R [1..n2 ] = A[m + 1..r ] 0. Loop invariant L[n1 + 1] = R [n2 + 1] = ∞ i =j =1 A[ℓ..k − 1] contains the k − ℓ for k = ℓ to r do smallest elements of L ∪ R sorted. if L[i ] ≤ R [j ] then A [k ] = L [i ] i =i +1 L[i ] and R [j ] are the smallest else elements in L and R which have not A [k ] = R [j ] been copied into A yet. j =j +1 1. Initialisation 2. Maintenance 3. Termination Therefore, Merge is correct! q.e.d. Run time? Merge makes exactly r − ℓ + 1 comparisons⋆. And MergeSort? Correct? Efficient?  8-1 MergeSort – an example MergeSort(int[ ] A, int ℓ = 1, int r = A.length) if ℓ < r then m = ⌊(ℓ + r )/2⌋ } divide MergeSort(A, ℓ, m) MergeSort(A, m + 1, r ) } conquer Merge(A, ℓ, m, r ) } combine  8-2 MergeSort – an example MergeSort(int[ ] A, int ℓ = 1, int r = A.length) if ℓ < r then m = ⌊(ℓ + r )/2⌋ } divide MergeSort(A, ℓ, m) MergeSort(A, m + 1, r ) } conquer Merge(A, ℓ, m, r ) } combine 1 5 6 10  8-3 MergeSort – an example MergeSort(int[ ] A, int ℓ = 1, int r = A.length) if ℓ < r then m = ⌊(ℓ + r )/2⌋ } divide MergeSort(A, ℓ, m) MergeSort(A, m + 1, r ) } conquer Merge(A, ℓ, m, r ) } combine 1 5 6 10 8 3 4 0 7 9 1 6 5 2  8-4 MergeSort – an example MergeSort(int[ ] A, int ℓ = 1, int r = A.length) if ℓ < r then m = ⌊(ℓ + r )/2⌋ } divide MergeSort(A, ℓ, m) MergeSort(A, m + 1, r ) } conquer Merge(A, ℓ, m, r ) } combine 1 5 6 10 8 3 4 0 7 9 1 6 5 2  8-5 MergeSort – an example MergeSort(int[ ] A, int ℓ = 1, int r = A.length) if ℓ < r then m = ⌊(ℓ + r )/2⌋ } divide MergeSort(A, ℓ, m) MergeSort(A, m + 1, r ) } conquer Merge(A, ℓ, m, r ) } combine 1 5 6 10 8 3 4 0 7 9 1 6 5 2 1 5 8 3 4 0 7  8-6 MergeSort – an example MergeSort(int[ ] A, int ℓ = 1, int r = A.length) if ℓ < r then m = ⌊(ℓ + r )/2⌋ } divide MergeSort(A, ℓ, m) MergeSort(A, m + 1, r ) } conquer Merge(A, ℓ, m, r ) } combine 1 5 6 10 8 3 4 0 7 9 1 6 5 2