What is the difference between oblivious and non-oblivious merging, sorting etc Algorithms can either be oblivious or non-oblivious, but what is the actual difference between the two?
Oblivious means that the control flow is independent of some properties of data. For example Bitonic Sort (also known as sorting net_ is oblivious, because it always compares the same elements disregarding data it gets, while Quick sort (or merge sort, or any adaptive sorting) are non-oblivious, because the algorithm steps change based on data. Bitonic sort does exactly the same steps in the best and the worst case, while non-oblivious algorithms may vary from $n$ steps to $n^2$ (for example).

This definition for cache is very similar, it means that it takes advantage of cache independently of its size (cache length).