Sorting and algorithms

As I have had previous experience dealing with fairly large SQL data sets, I've noticed the large dependencies in the return time of SQL queries. Alghorithm analysis as we have covered them in class seem to address the reasons behind these differences in "efficiency". What was most interesting was the multiples ways one could choose to sort through a list of items and how one sorting alghorithm may have advantages over another depending on the size of the items. As I've taken CSC165 in the fall, I've an understanding of how algorithm analysis relates to iterative functions; but, as has been the case throughout the semester, recursive algorithms, namely the merge sort, serve as the most interesting examples for analysis.

Binary search trees are awesome as any inorder traversal of their nodes will provide a sorted list of numbers. While BSTs seem to be extremely efficient for searching alghorithms, considering the fact that they will on average disregard half of the nodes in the tree, I'm confused on whether or not a BST can best a merge sort as building a tree out of list of numbers and that traversing through it seems rather costly.

To Reduce, Reuse and Recycle[Trees?]

I may be wrong in my thinking, but the only distinction that I have been able to see between reduction and my limited experience with mathematical induction; is that induction appears to be limited to the set of natural numbers. Initially, I had issues with recursion examples that didn't involve recursively calling a function a single decrementing parameter; such as the problem of the Tower of Anne Hoy. But the true power of reduction was made clear in how they were used in traversing trees. It was natural for me to visualize a small team of electronic insects scouring their way down each individual branch and returning their individual spoils back in to a larger pot. Reduction is pretty neat when your dealing with a problem that can be easily divided in to smaller sub-sets, as it creates code that is easy on the eyes and strangely intuitive, I say strange because of how non-intuitive recursion was to me originally. Based on the course website for last semester, it looks like recursive data structures will be the major topic for the rest of this semester, so I'm looking forward to gaining further insights on this nifty tool.