Wave Sort - Sort an array in wave form in linear time. Important interview question asked in companies like Google, Paytm, Amazon, GS etc.

Time Complexity is O(n)

using namespace std;

int main(){

    int a[] = {0,1,2,3,4,5};
    int n = sizeof(a)/sizeof(int);

    ///Go to every 2nd element, try to create a peak
    for(int i=0;i<n;i+=2){

        ///Check for Left Element
        if(i>0 && a[i-1]>a[i]){
        ///Check for the right element
        if(i<=n-2 && a[i+1]>a[i]){

    ///Print the array
    for(int i=0;i<n;i++){
        cout<<a[i]<<" ";

return 0;