I am trying to sort an array which has properties like

it increases upto some extent then it starts decreasing, then increases and then decreases and so on. Is there any algorithm which can sort this in less then nlog(n) complexity by making use of it being partially ordered?

array example = 14,19,34,56,36,22,20,7,45,56,50,32,31,45......... upto n

Thanks in advance

You could find the change / partition points, and perform a merge sort between pairs of partitions. This would take advantage of the existing ordering, as normally the merge sort starts with pairs of elements.

**Edit** Just trying to figure out the complexity here. Merge sort is n log(n), where the log(n) relates to the number of times you have to re-partition. First every pair of elements, then every pair of pairs, etc... until you reach the size of the array. In this case you have n elements with p partitions, where p < n, so I'm guessing the complexity is p log(p), but am open to correction. e.g. merge each pair of paritions, and repeat based on half the number of partitions after the merge.

Any sequence of numbers will go up and down and up and down again etc unless they are already fully sorted (May start with a down, of course). You could run through the sequence noting the points where it changes direction, then then merge-sort the sequences (reverse reading the backward sequences)

In general the complexity is N log N because we don't know how sorted it is at this point. If it is moderately well sorted, i.e. there are fewer changes of direction, it will take fewer comparisons.

If you know for a fact that the data are "almost sorted" and the set size is reasonably small (say an array that can be indexed by a 16-bit integer), then Shell is probably your best bet. Yes, it has a basic time complexity of O(n^2) (which can be reduced by the sequence used for gap sizing to a current best-worst-case of O(n*log^2(n))), but the performance improves with the sortedness of the input set to a best-case of O(n) on an already-sorted set. Using Sedgewick's sequence for gap size will give the best performance on those occasions when the input is not as sorted as you expected it to be.

Strand Sort might be close to what you're looking for. O(n sqrt(n)) in the average case, O(n) best case (list already sorted), O(n^2) worst case (list sorted in reverse order).

Share and enjoy.

Similar Questions

I have an array with a list of objects sorted alphabetically ignoring the letters case (used a lowerCaseString method) and I need to sort it into an array of arrays one for each letter +1 for non alph

We know that several sorts, such as insertion sort, are great on arrays that are 'mostly-sorted' and not so great on random data. Suppose we wanted to profile the performance improvement/degradation o

Say you have an array of document ids stored elsewhere (e.g. in Redis sorted set). What is the most efficient way of querying Mongo documents with { _id: { $in: ids }} and having the results sorted in

How to get some value which specifies which column the data is sorted by (and whether it's ascending or descending) in QTableWidget? I couldn't find anything in the documentation about it, only about

I've had trouble with the examples in the PHP manual, so I'd like to ask this here... I have an array of objects.. Is there a way to sort it based on the contents of the object? For example, my array

I am having trouble getting the array to sort after the random numbers are generated in the array. I think the array is being sorted before all the numbers are assigned. I have tried nesting another f

I have a getSortedIndex function. The function accepts the following arguments: An array of objects which are sorted by a key. A new object to be inserted into the array. The key by which all objects

I have an array, $items, which contains lot of informations: name, size, quantity, color, id... I'm using 'for' loops to sort $items values by color and save the sorted values in a new array, But the

How can I sort a query by the number of elements of an array field? Let say I have records like { title: '', author: '', votes: [id,id,id] } I would like to do sort by the length of the array votes

Hi I have a bubble sort method that takes my array of strings and sorts them. However I want the sorted strings to be entered into another array so that the original unsorted array can be used for oth

My Project is in Java Swing. I have a JPanel on which I am adding some images with .png extension (which are on JLabels) at center. Now I want to add a line which will be partially on the JPanel &

This question already has an answer here: Python sorting list of dictionaries by multiple keys 6 answers How can I sort a list of dictionary by two keys, in which the second key should be sorte

Is it possible to sort my MongoDB array of reviews by the date the review was made? Would I have to do this in my server-side script rather than by using a query operator? If so how would I do that? {

I have a document with the following structure: { tags: ['bbb', 'aaa', 'ddd', 'ccc'] } and I want to create a view which returns the hash of the sorted tags array as key. My approach is to sort the t

Can anybody optimize following statement in Scala: // maybe large val someArray = Array(9, 1, 6, 2, 1, 9, 4, 5, 1, 6, 5, 0, 6) // output a sorted list which contains unique element from the array with

I am trying to write the Array.sort method in my own way using recursive logic. My code is as follows: def sorting_array(unsorted,sorted) temp=unsorted if unsorted.length==0 return sorted elsif unsort

I have a NSMutableArray. It contains NSIndexPaths which itself a NSUInteger array. Array looks like this [ (NSIndexPath xxxxxxx) 3 indexes [1, 0, 0], (NSIndexPath xxxxxxx) 3 indexes [2, 1, 1], (NSIn

I have an NSMutableArray which holds the dates in format dd/MM/yyyy of type NSString. Now i need to display the sorted array of dates. Please suggest me how to achieve it. Thank You.

for F# array, is there an easy way to return sorting indices along with the sorted array? like the sort() function from Matlab? Background: I came from matlab/R, where manipulating array on indices ar

I want to sort two already sorted arrays into one. I am using merge sort for this purpose. Error:: IndexError: list index out of range I have tried checking out this manually and I couldnt find out of

I have an array of strings which need to be sorted by multiple criteria (two string attributes). However the two sorts need to be sorted in opposite directions. Example: Array must be sorted by attr

I have a predefined list which indicates the order of some values: ['id','name','age','height','weight',] (can be very long) I want to sort any subset of this list: So if i get ['height','id'] It wi

i don't have much clue of C but i want to understand how this code works. My Problem is that i really don't understand how the vector can be sorted in this case. How does it know by which value it has

I have an array of objects that I want to sort by random. For this case I can use array.shuffle. But what if I want to reproduce that order later on the same array? Is there any way that I can provide

Need Hints to design an efficient algorithm that takes the following input and spits out the following output. Input: two sorted arrays of integers A and B, each of length n Output: One sorted array t

I have NSMutableArray in which all object is in NSMutableDictionary i want to sort this array base on NSMutableDictionary with two key one is country and another is name. Can any one Help me to use NS

I have an associative array in following format.I need to sort the array in descending order and sort the array with same value as ascending order. $numArray = array(); $numArray[0]['Word'] = 'One'; $

I need a PHP script which would sort an array of numbers by first digit, then by second digit, and so on. For example, an array: $arr = array(1, 94, 4, 925, 401, 277, 255); should result in a sort li

I have a puzzle, input var a = ['a', 'b', 'c', 'd'], b = [1, 0, 3, 2]; output ['b', 'a', 'd', 'c'] My solution looks like this function _sort(array, rules) { var i, len = rules.length, res = [] if

I have this array, which is already sorted by 'name' ASC. array 0 => array 'id' => '4' 'name' => 'iPad' 'games' => 5 1 => array 'id' => '5' 'name' => 'iPhone' 'games' => 5 2 =&

In R, given an numeric array, how to produce another array which contains sorted index order into the original array? To clarify my question, consider an example: For an original array: [33 11 55 22 4

I am trying to build a program that accepts an array of integers as parameter and return a string. The string would be ascending if the array is sorted from the smallest to the greatest, descending

I have this code that I have been working on for a couple of hours now trying to figure out how to implement removing duplicates within the sorted array during the insertion sort. I'm trying to do thi

Note: I'm using ruby 1.9.3 and I can't bring any external dependencies. I have to do this with the core lib. @run_histogram is a Hash of names to an Array of values (two values at this time, :failure,

Is there an optimized function in any numerical library (MKL, Boost, GSL,..etc) that searches a sorted array of floating point numbers for the closest match to a given float? Another function which wi

which is the best sorting method? To sort using array or dictionary sort? If array or dictionary, why so?

What is an easy way in Java to sort the array of elements maintaining information about indexes where the elements were stored in the original array? Is there a built-in function? There are few ways I

I need a float[] to be sorted. And I need to know where the old indices are in new array. That's why I can't use Array.Sort(); or whatever. So I would like to write a function that sorts the array for

I have a list [[0, 3], [5, 1], [2, 1], [4, 5]] which I have made into an array using numpy.array: [[0 3] [5 1] [2 1] [4 5]] How do I sort this like a table? In particular, I want to sort by the seco

I noticed a strange behavior (for me) when sorting a list retrieved with Arrays.asList(). It seems that after Collections.sort( list ), the origin array is also sorted ! How is it possible ? List<R

Possible Duplicate: How do I sort a multidimensional array in php I have value array and want to sort the value based on alphabetical order my current array $original_array = array( array('id' =&g

I have a CoreData store and am looking to maintain a sort order as provided by a REST service. The objects in CoreData have a guid attribute and the REST-provided array (of GUIDs) is sorted. I would l

[This is an interview question. I couldn't find a duplicate.] An array contains two sub- sorted arrays. Give an inplace algorithm to sort two sub arrays. for ex: I/P: 1 4 5 7 8 9 2 3 6 10 11 O/P: 1 2

I need to write a java linked list which needs to be array based and sorted. So the array contains nodes which have 2 fields: the data, and the index of the next element in the list. The last element

The problem: Consder the following floats[]: d[i] = 1.7 -0.3 2.1 0.5 What I want is an array of int[] that represents the order of the original array with indices. s[i] = 1 3 0 2 d[s[i]] = -0.3 0.5 1

Does the Collections.sort(list) check if the list is already sorted or is it maybe O(1) for some other reason? Or, is it a good idea to have a flag sorted and set it to true/false upon calling sort()/

The Idea is to create a method that is static that will calculate the average salary for a partially-filled array. Assume that numEmployees holds the number of elements in the array that have valid da

I have a sorted integers of over a billion, which data structure do you think can exploited the sorted behavior? Main goal is to search items faster... Options I can think of -- 1) regular Binary Se

I have an n x m array that I need sorted. However, I only need to look at the first value of each 1d array to sort the larger array. For example, consider the following 2d array: [[1, 2], [4, 4], [3,

I am trying to sort a multi dimensional array, and have one value always at the end of the array. The array should be sorted by 'unitText' (dont care how unitID is sorted), but always have Last as t