Skip to content

Instantly share code, notes, and snippets.

@millermedeiros
Created February 21, 2011 22:02
  • Star 2 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save millermedeiros/837780 to your computer and use it in GitHub Desktop.
Simple Sorted Insertion
/**
* Add items to Array in a sorted order.
* @param {Array} arr
* @param {Number} item
* @author Miller Medeiros
* Released under the WTFPL (http://sam.zoy.org/wtfpl/)
*/
function sortedInsert(arr, item){
var n = arr.length;
do { n--; } while (item < arr[n]);
arr.splice(n+1, 0, item);
}
// Usage Example ------------------------------
//=============================================
var my_array = [0, 2, 8, 32, 64];
sortedInsert(my_array, 9); //-> [0, 2, 8, 9, 32, 64]
sortedInsert(my_array, 1); //-> [0, 1, 2, 8, 9, 32, 64]
sortedInsert(my_array, 67); //-> [0, 1, 2, 8, 9, 32, 64, 67]
@millermedeiros
Copy link
Author

Created since most implementations that I could find use nested loops and sort existing items of the array - a.k.a. Insertion Sort - which in some cases is unnecessary (if the array is already sorted or empty).

IMPORTANT: this code doesn't sort the items of the array, it only inserts new items in the proper order. Only use it if you are sure that the items of the array are already sorted or if it is an empty array.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment