# libavutil/qsort.h File Reference

`#include "common.h"`

Go to the source code of this file.

## Defines

#define AV_QSORT(p, num, type, cmp)
Quicksort This sort is fast, and fully inplace but not stable and it is possible to construct input that requires O(n^2) time but this is very unlikely to happen with non constructed input.
#define AV_MSORT(p, tmp, num, type, cmp)
Merge sort, this sort requires a temporary buffer and is stable, its worst case time is O(n log n).

## Define Documentation

 #define AV_MSORT ( p, tmp, num, type, cmp )

Value:

```{\
unsigned i, j, step;\
for(step=1; step<(num); step+=step){\
for(i=0; i<(num); i+=2*step){\
unsigned a[2] = {i, i+step};\
unsigned end = FFMIN(i+2*step, (num));\
for(j=i; a[0]<i+step && a[1]<end; j++){\
int idx= cmp(p+a[0], p+a[1]) > 0;\
tmp[j] = p[ a[idx]++ ];\
}\
if(a[0]>=i+step) a[0] = a[1];\
for(; j<end; j++){\
tmp[j] = p[ a[0]++ ];\
}\
}\
FFSWAP(type*, p, tmp);\
}\
}
```
Merge sort, this sort requires a temporary buffer and is stable, its worst case time is O(n log n).

Parameters:
 p must be a lvalue pointer, this function may exchange it with tmp tmp must be a lvalue pointer, this function may exchange it with p

Definition at line 100 of file qsort.h.

 #define AV_QSORT ( p, num, type, cmp )

Quicksort This sort is fast, and fully inplace but not stable and it is possible to construct input that requires O(n^2) time but this is very unlikely to happen with non constructed input.

Definition at line 30 of file qsort.h.

Generated on Fri Oct 26 02:50:12 2012 for FFmpeg by  1.5.8