php实现二路归并排序

<span> 1</span><span>$arr</span> = [9, 43, 12, 0, 87, 1<span>];
</span><span> 2</span><span>function</span> merge_sort(&<span>$arr</span><span>){
</span><span> 3</span>     _merge_sort(<span>$arr</span>, <span>$arr</span>, 0, <span>count</span>(<span>$arr</span>) - 1<span>);
</span><span> 4</span><span>}
</span><span> 5</span><span> 6</span><span>function</span> _merge_sort(&<span>$s_arr</span>, &<span>$d_arr</span>, <span>$i</span>, <span>$j</span><span>){
</span><span> 7</span><span>if</span>(<span>$i</span> > <span>$j</span><span>){
</span><span> 8</span><span>return</span><span>;
</span><span> 9</span><span>    }
</span><span>10</span><span>if</span>(<span>$i</span> == <span>$j</span><span>){
</span><span>11</span><span>echo</span> 'aa'<span>;
</span><span>12</span><span>$d_arr</span>[<span>$i</span>] = <span>$s_arr</span>[<span>$i</span><span>];
</span><span>13</span><span>return</span><span>false</span><span>;
</span><span>14</span><span>    }
</span><span>15</span><span>$tmp_arr</span> = <span>array</span><span>();
</span><span>16</span><span>$m</span> = <span>intval</span>((<span>$i</span> + <span>$j</span>)/2<span>);
</span><span>17</span><span>echo</span><span>$m</span><span>;
</span><span>18</span><span>if</span>(<span>$i</span> <= <span>$m</span><span>){
</span><span>19</span>         _merge_sort(<span>$s_arr</span>, <span>$tmp_arr</span>, <span>$i</span>, <span>$m</span><span>);
</span><span>20</span><span>    }
</span><span>21</span><span>if</span>(<span>$m</span>+1 <= <span>$j</span><span> ){
</span><span>22</span>         _merge_sort(<span>$s_arr</span>, <span>$tmp_arr</span>, <span>$m</span>+1, <span>$j</span><span>);
</span><span>23</span><span>    }
</span><span>24</span>     merge(<span>$tmp_arr</span>, <span>$d_arr</span>, <span>$i</span>, <span>$m</span>, <span>$j</span><span>);
</span><span>25</span><span>}
</span><span>26</span> //$s_arr中的$start到$m与$m到$end两个序列都是有序的，将这两个序列合并到$d_arr里面
<span>27</span><span>function</span> merge(&<span>$s_arr</span>, &<span>$d_arr</span>, <span>$start</span>, <span>$m</span>, <span>$end</span><span>){
</span><span>28</span><span>$i</span> = <span>$start</span>; <span>$j</span> = <span>$m</span>+1;<span>$d_i</span> = <span>$i</span><span>;
</span><span>29</span><span>while</span>(<span>$i</span> <= <span>$m</span> && <span>$j</span> <= <span>$end</span><span>){
</span><span>30</span><span>if</span>(<span>$s_arr</span>[<span>$i</span>] > <span>$s_arr</span>[<span>$j</span><span>]){
</span><span>31</span><span>$d_arr</span>[<span>$d_i</span>++] = <span>$s_arr</span>[<span>$i</span>++<span>];
</span><span>32</span><span>//</span><span>$i++;</span><span>33</span>         }<span>else</span><span>{
</span><span>34</span><span>$d_arr</span>[<span>$d_i</span>++] = <span>$s_arr</span>[<span>$j</span>++<span>];
</span><span>35</span><span>        }
</span><span>36</span><span>    }
</span><span>37</span><span>while</span>(<span>$i</span> <= <span>$m</span><span>){
</span><span>38</span><span>$d_arr</span>[<span>$d_i</span>++] = <span>$s_arr</span>[<span>$i</span>++<span>];
</span><span>39</span><span>//</span><span>$i++;</span><span>40</span><span>    }
</span><span>41</span><span>while</span> (<span>$j</span> <= <span>$end</span><span>) {
</span><span>42</span><span>$d_arr</span>[<span>$d_i</span>++] = <span>$s_arr</span>[<span>$j</span>++<span>];
</span><span>43</span><span>    }
</span><span>44</span> }