Про пузырьковую сортировку.

[thesz]

Вот сортировка пузырьком:
void bubble_sort(int *arr,int len) {
int i,j;
for (i=0;i < len-1;i++)
for (j=0;j < len-1-i;j++) {
if (arr[j] > arr[j+1]) {
int t = arr[j];
arr[j] = arr[j+1];
arr[j+1] = t;
}
}
} /* bubble_sort */Каждая итерация зависит от предыдущей в обеих циклах.

Зависит умеренно хитро:

(0,3)
|
(0,2) - (1,2)
| / |
(0,1) - (1,1) - (2,1)
| / | / |
(0,0) - (1,0) - (2,0) - (3,0)Выход (i,j) влияет на входы (i,j+1), (i+1,j) и (i+1,j+1).

А что будет, если перебирать индексы так, чтобы их сумма была постоянна? Вот так:
- итерация 0: (0,0),
- итерация 1: (0,1), (1,0),
- итерация 2: (0,2), (1,1), (2,0),
- итерация 3: (0,3), (1,2), (2,1) и (3,0).

Внезапно исчезает зависимость между итерациями внутреннего цикла - от (i,j) зависят (i+(0|1),j+(0|1)), а их сумма всегда больше текущей и, значит, они принадлежат следующей итерации.

Получается, что части внутреннего цикла могут быть выполнены параллельно.

Как это формализовать, не знаю. ;)

В принципе, это перекошивание циклов (loop skewing). Но как догадаться, в какую сторону наклонять...