| OLD | NEW |
| 1 // Copyright 2006-2008 the V8 project authors. All rights reserved. | 1 // Copyright 2006-2008 the V8 project authors. All rights reserved. |
| 2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
| 3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
| 4 // met: | 4 // met: |
| 5 // | 5 // |
| 6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
| 7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
| 8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
| 9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
| 10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
| (...skipping 665 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 676 return; | 676 return; |
| 677 } | 677 } |
| 678 var pivot_index = $floor($random() * (to - from)) + from; | 678 var pivot_index = $floor($random() * (to - from)) + from; |
| 679 var pivot = a[pivot_index]; | 679 var pivot = a[pivot_index]; |
| 680 // Pre-convert the element to a string for comparison if we know | 680 // Pre-convert the element to a string for comparison if we know |
| 681 // it will happen on each compare anyway. | 681 // it will happen on each compare anyway. |
| 682 var pivot_key = | 682 var pivot_key = |
| 683 (custom_compare || %_IsSmi(pivot)) ? pivot : ToString(pivot); | 683 (custom_compare || %_IsSmi(pivot)) ? pivot : ToString(pivot); |
| 684 // Issue 95: Keep the pivot element out of the comparisons to avoid | 684 // Issue 95: Keep the pivot element out of the comparisons to avoid |
| 685 // infinite recursion if comparefn(pivot, pivot) != 0. | 685 // infinite recursion if comparefn(pivot, pivot) != 0. |
| 686 var low_end = from; // Upper bound of the elements lower than pivot. | 686 a[pivot_index] = a[from]; |
| 687 var high_start = to; // Lower bound of the elements greater than pivot. | 687 a[from] = pivot; |
| 688 var eq_start = to - 1; // Lower bound of elements equal to pivot. | 688 var low_end = from; // Upper bound of the elements lower than pivot. |
| 689 a[pivot_index] = a[eq_start]; | 689 var high_start = to; // Lower bound of the elements greater than pivot. |
| 690 a[eq_start] = pivot; | 690 // From low_end to i are elements equal to pivot. |
| 691 // From eq_start to high_start are elements equal to the pivot | 691 // From i to high_start are elements that haven't been compared yet. |
| 692 // (including the pivot). | 692 for (var i = from + 1; i < high_start; ) { |
| 693 // From low_end to eq_start are elements that have not been compared yet. | 693 var element = a[i]; |
| 694 while (low_end < eq_start) { | |
| 695 var element = a[low_end]; | |
| 696 var order = Compare(element, pivot_key); | 694 var order = Compare(element, pivot_key); |
| 697 if (order < 0) { | 695 if (order < 0) { |
| 696 a[i] = a[low_end]; |
| 697 a[low_end] = element; |
| 698 i++; |
| 698 low_end++; | 699 low_end++; |
| 699 } else if (order > 0) { | 700 } else if (order > 0) { |
| 700 eq_start--; | |
| 701 high_start--; | 701 high_start--; |
| 702 a[low_end] = a[eq_start]; | 702 a[i] = a[high_start]; |
| 703 a[eq_start] = a[high_start]; | |
| 704 a[high_start] = element; | 703 a[high_start] = element; |
| 705 } else { // order == 0 | 704 } else { // order == 0 |
| 706 eq_start--; | 705 i++; |
| 707 a[low_end] = a[eq_start]; | |
| 708 a[eq_start] = element; | |
| 709 } | 706 } |
| 710 } | 707 } |
| 711 QuickSort(a, from, low_end); | 708 QuickSort(a, from, low_end); |
| 712 QuickSort(a, high_start, to); | 709 QuickSort(a, high_start, to); |
| 713 } | 710 } |
| 714 | 711 |
| 715 var old_length = ToUint32(this.length); | 712 var old_length = ToUint32(this.length); |
| 716 if (old_length < 2) return this; | 713 if (old_length < 2) return this; |
| 717 | 714 |
| 718 %RemoveArrayHoles(this); | 715 %RemoveArrayHoles(this); |
| (...skipping 213 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 932 ArrayEvery: 1, | 929 ArrayEvery: 1, |
| 933 ArrayMap: 1, | 930 ArrayMap: 1, |
| 934 ArrayIndexOf: 1, | 931 ArrayIndexOf: 1, |
| 935 ArrayLastIndexOf: 1, | 932 ArrayLastIndexOf: 1, |
| 936 ArrayPush: 1 | 933 ArrayPush: 1 |
| 937 }); | 934 }); |
| 938 } | 935 } |
| 939 | 936 |
| 940 | 937 |
| 941 SetupArray(); | 938 SetupArray(); |
| OLD | NEW |