Question

Select 1 topic from among the 6 listed below, and in at least 400 words, write a post that explains your chosen topic.

Additional resources are listed in the Reading & Study folder of this Module/Week.

1. Query Optimizer Overview

              Query Optimization Steps

              *Be sure to address the question “What are the algorithm categories?”

2. Algorithms Introduction

              External Sort/Merge

              *Be sure to explain how the merge/sort algorithm works.

3. Select Algorithms - Simple

              *Be sure to discuss Algorithms S1-S7.

4. Select Algorithms - Complex

*Be sure to discuss Algorithms S8-S11.

5. Join Operation Algorithms

              *Be sure to explain Algorithms J1-J5

6. Optimization Techniques

              *Be sure to discuss Cost vs. Heuristic based optimization

Answer 1

2. Algorithm Introduction:

Merge Sort:

Goal of general sorting algorithm is:

1. Arrange elements in predetermined order
   • Based on key for each element
2. Derived from ability to compare two keys by size

Properties of Merge sort:

1. Stable -> relative order of equal keys unchanged
2. In-place -> uses only constant additional space
3. External -> can efficiently sort large # of keys

Approach

1. Partition list of elements into 2 lists
2. Recursively sort both lists
3. Given 2 sorted lists, merge into 1 sorted list
   • Examine head of both lists
   • Move smaller to end of new list

Performance

1. O( n log(n) ) average / worst case

IDEA:
Merge Sort algorithm is based on a divide and conquer strategy.

1. Divide: The sequence to be sorted is decomposed into two halves.
2. Conquer: Each half is sorted independently
3. Combine: Then the two sorted halves are merged to a sorted sequence

Time Complexity:
Suppose that n = 2k for some entire k. Let T(n) the time used to sort n elements. As we
can perform separation and merging in linear time, it takes cn time to perform these two steps,
for some constant c. So,
T(n) = 2T(n/2) + cn.
In the same way:
T(n/2) = 2T(n/4) + cn/2, so
T(n) = 4T(n/4) + 2cn.
Going in this way ...
T(n) = 2mT(n/2m) + mcn, and
T(n) = 2kT(n/2k) + kcn = nT(1) + cnlog2n = O(n log n).

Pseudo Code:

divide(int a[], int low, int high)

   if(low<high)

{

mid = (low+high)/2

divide(a, low, mid)

     divide(a, mid+1,high)

     Merge(A, low, mid, high)

}

Merge(A,Low,mid,high)

S ← empty sequence
while A.isEmpty() ∧ B.isEmpty()
if A.first().element() < B.first().element()
S.insertLast(A.remove(A.first()))
else
S.insertLast(B.remove(B.first()))
while ¬A.isEmpty()
S.insertLast(A.remove(A.first()))
while ¬B.isEmpty()
S.insertLast(B.remove(B.first()))
return S