[Solved]: What is the difference between oblivious and non-oblivious merging, sorting etc

Problem Detail: 

Algorithms can either be oblivious or non-oblivious, but what is the actual difference between the two?

Asked By : Summer

Answered By : Evil

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).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/58031