# Introduction nformation growth rapidly in our world and to search for this information, it should be ordered in some sensible order. Many years ago, it was estimated that more than half the time on many commercial computers was spent in sorting. Fortunately this is no longer true organizing data, methods which do not require that the data be kept in any special order [1]. Many algorithms are very well known for sorting the unordered lists. Most important of them are Bubble, Heap, Merge, Selection [2]. As stated in [3], sorting has been considered as a fundamental problem in the study of algorithms, that due to many reasons: 1. The need to sort information is inherent in many applications. 2. Algorithms often use sorting as a key subroutine. 3. In algorithms design there are many essential techniques represented in the body of sorting algorithms. 4. Many engineering issues come to the fore when implementing sorting algorithms. Efficient sorting algorithms is important to optimize the use of other algorithms that require sorted lists to work correctly; it is also often in producing human readable output. Formally, the output should satisfy two major conditions: 1. The output is in non-decreasing order. 2. The output is a permutation or reordering of the input. Since the early beginning of computing, the sorting problem has attracted many researchers, perhaps due to the complexity of solving it efficiently. Bubble sort was analyzed as early as 1956 [6]. Author ? ? : Assistant Professor, Department of Information Science & Engineering Jyothy Institute of Technology, Bangalore. e-mails: anshu.garg13@gmail.com, goyal.garima18@gmail.com introductory computer science classes, where the abundance of algorithm for the problem provides a gentle introduction of core algorithm concepts [4,5]. In [4], they classified sorting algorithms by: 1. Computational complexity ( # Input Sort a) Concept A simple sorting algorithm which sort the data whenever it is input from any input source e.g. keyboard or data from a stream of file. when new item comes then it is inserted at its specific position through a recursive function if there are n elements then n items 1 at a time is inserted in array which increase array size automatically and take its appropriate position. # GET_INPUT( ) for i = 1 to n { scan(c[i]) call INPUT_SORT(c[i],1,size+1) } end III. # Working # Suppose we have array c[1?5] of five elements as follows: First we call GET_INPUT() function and read input from input source Which is Sorted Array . IV. # Complexity Generally the complexity of an algorithm is measured in two phases. When one measures the complexity of an algorithm by pen and paper, he/she can only predict the complexity which give an idea how much time and space this algorithm takes to finish in its execution. This phase is called priory analysis. After implementing the algorithm in computer, we get the actual time and space. This phase of analyzing the algorithm is called the posterior analysis. complexity of an algorithm can be of two types: 1. Time Complexity: The analysis of algorithm for the prediction of computation time for execution of each and every instruction in the algorithm is called the time complexity. ![During 1st Pass: insert 5 call INPUT_SORT(1,1) Content of array c[size] i.e c[1] 5 P=1,q=1,r=1,size=1 During 2nd Pass: insert 4 call INPUT_SORT(1,2) Content of array c[size] i.e c[2During 5th Pass: insert 4 call INPUT_SORT(1,5) Content of array c[size] i.e c[](image-2.png "") Somesorting algorithms are "in-place", such that onlyO(1)or O(log n)memory is needed beyond the itemsbeing stored, while others need to create auxiliarylocations for data to temporally stored.3. Recursion some algorithms are either recursive ornon recursive, while others may be both (e.g mergesort).4. Whether or not they are a comparison sort. Acomparison sort examines the data only bycomparing two elements with a comparisonoperator.This paper presents a new sorting algorithmcalled input sort. Its typical use is when sorting theelements of a stream from file.II. An Optimized Input Sorting AlgorithmYear 201612Volume XVI Issue I Version I( )Global Journal of Computer Science and TechnologyUsingthestandardrecurrenceequationT(n)=aT[n/b]+f(n) get this equation:T(n)=2T[n/2]+na=2 b=2 f(n)=nn log alog 2 b = n 2 = nusing master method's 2 nd case applyHSortingBest Case © 2016 Global Journals Inc. (US) if f(n)=? (n log a b), then T(n)= ? (n log a b . log n) Time complexity of Input Sort is T(n)= ? ( n logn) ## VI. comparison with heap and merge sort Now if we talk about heap merge sort than our algorithm is better from two in the sense that In merge sort we need two extra temporary array which increase its space complexity but no need of extra memory in our algorithm. our algorithm has order of O(nlog n) but it execute fast because of less comparisons than Merge heap and Quick sort. ## VII. ## Conclusion In this paper new sorting algorithm is presented INPUT-SORT has O(nlog n) complexity but it is faster than existing sort mentioned in section 4 in detail. INPUT-SORT is definitely faster than other sort to sort n elements. Furthermore, the proposed algorithms are compared with some recent sorting algorithms; selection sort and bubble sort, heap, merge, insertion, quick sort. These algorithm can be applied on a real world application. any sorting algorithm might be a subroutine of another algorithms which affects its complexity. * The Art Of Computer Programming DKnuth 1998 Addison Wesley * Enhanched Shell Sorting Algorithm BShahzad MAfzal computer general of Enformatika 21 6 2007 * Introduction to Algorithms TCormen CLeisersion RRivest CStein 2001 McGraw Hill * the design and analysis of computer Algorithms AAho JHopcroft UllmanJ 1974 Addison Wesley * Randomized Sorting in O(n log log n) Time And Linear Space Addition, Shift, and Bit Wise Boolean Operations MThoroup Computer Journal of Algo rithms 42 2 2002 * Bubble Sort: An Archaeological Algorithmic Analysis OAstrachanm 2003 Duk University