合并排序非递归实现总结

合并排序在众多排序算法中算是比较稳定的排序算法，时间复杂度为nlogn，采取分治的思想，可以说是比较高效的的排序算法。
开始将长度为len的数组分为长度为1的len个子序列，开始作如下按照从小到大顺序合并：

直到合并成一个长度和正数组长度相等的子序列即可。

---

下面是代码的非递归实现实现：

#include <iostream>
#include<vector>
using namespace std ;


void merge(vector<int>&ls, vector<int>&tmp, int l, int m, int r) {
    int left = l ;
    int k = l ;
    int mid = m+1 ;
    //将当前段的元素转移到ｔｍｐ数组中相应位置
    while(left<=m&&mid<=r) {
        
        if(ls[left] > ls[mid]) {
            tmp[k++] = ls[mid++];
        }
        else {
            tmp[k++] = ls[left++] ;
        }   
    }

    if(left <= m) {
        while(left <= m) {
            tmp[k++] = ls[left++] ;
        }
    }
    else {
        while(mid<=r) {
            tmp[k++] = ls[mid++] ;
        }
    }       
}

void mergePass(vector<int>&ls, vector<int>&tmp, int s, int n) {
    int i= 0;   

    while(i<=n-2*s) {
        //将前一组长度为s个元素合并
        merge(ls, tmp, i, i+s-1, i+2*s-1) ;
        i = i+2*s ;
    }
    //剩余的元素少于3s的话
    if(i+s<n) {
        merge(ls, tmp, i, i+s-1, n-1) ;
    }

    else {
        for(int k=i; k<=n-1; k++) {
            tmp[k] = ls[k] ;
        }
    }
}

//合并排序非递归
void mergeSort(vector<int>&ls) {   
    vector<int>tmp =ls ;
    int s= 1 ;
    int len = ls.size();
    while(s<len) {
        mergePass(ls, tmp, s, len) ;
        s+=s ;
        mergePass(tmp, ls, s, len) ;
        s+=s ;
    }
}

int main()
{
    vector<int>ls ;
    while(1) {
        int n ;
        cin >> n ;
        if(n == -1) {
            break ;
        }
        ls.push_back(n) ;
    }

    mergeSort(ls) ;
    for(int i=0; i<(int)ls.size(); i++) {
        cout << ls[i] <<"  "  ;
    }
    return 0;
}