-------------------------------------------------------------------------------- PROGRAM Introsort -------------------------------------------------------------------------------- INFORMATION -------------------------------------------------------------------------------- Introsort or introspective sort is a hybrid sorting algorithm that provides both fast average performance and (asymptotically) optimal worst-case performance. It begins with quicksort, it switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted and it switches to insertion sort when the number of elements is below some threshold. This combines the good parts of the three algorithms, with practical performance comparable to quicksort on typical data sets and worst-case O(n log n) runtime due to the heap sort. Since the three algorithms it uses are comparison sorts, it is also a comparison sort. -------------------------------------------------------------------------------- CHARACTERISTICS -------------------------------------------------------------------------------- Average and worst: O(n log n). Space: O(log n) for in-place implementations. Stable: No. -------------------------------------------------------------------------------- LANGUAGES TO IMPLEMENT IN -------------------------------------------------------------------------------- # LANGUAGE IDE -- --------- ---------------------------------------------- 01 Ada GNAT Studio 02 BASIC GW-BASIC 03 C\C++ Borland C++ 04 C++ .NET Visual Studio 05 C# Visual Studio 06 COBOL OpenCobolIDE 07 Java Eclipse 08 Lua ZeroBrane Studio 09 Pascal Turbo Pascal 10 Perl Notepad++ -> Command Line 11 PowerShell Notepad++ -> Windows PowerShell 12 Python Idle 13 VB .NET Visual Studio 14 x64 Assembly GUI Turbo Assembler ---6502 Atari--- 15 Atari BASIC Atari BASIC Editor 16 C Deep Blue C ---68000 Atari--- 17 68000 Assembly GFA Assembler for Atari ST 18 GFA Basic GFA Basic Atari ST 19 C HiSoft C Atari ST -------------------------------------------------------------------------------- METHODS/FUNCTIONS (Pseudocode from https://en.wikipedia.org/wiki/Introsort) -------------------------------------------------------------------------------- procedure sort(A : array): maxdepth <- log2(length(A)) × 2 introsort(A, maxdepth) procedure introsort(A, maxdepth): n <- length(A) if n < 16: insertionsort(A) else if maxdepth = 0: heapsort(A) else: p ← partition(A) // assume this function does pivot selection, p is the final position of the pivot introsort(A[1:p-1], maxdepth - 1) introsort(A[p+1:n], maxdepth - 1) -------------------------------------------------------------------------------- procedure insertionsort(A) is for index <- 1 to length(A) - 1 do value <- A[index] position <- index - 1 while position >= 0 and A[position] > value do A[position + 1] <- A[position] position <- position - 1 A[position + 1] <- value -------------------------------------------------------------------------------- procedure heapsort(A) is build a max heap from A repeatedly move the root to the end and restore the remaining max heap -------------------------------------------------------------------------------- function partition(A) is choose a pivot and move it to the end of A move values less than or equal to the pivot before it move the pivot to its final position return the pivot's final index -------------------------------------------------------------------------------- SEE ALSO: Heapsort.txt -------------------------------------------------------------------------------- function readSortingInput(filePath) is values <- empty array open filePath for reading for each line in filePath do append integer(line) to values close filePath return values --------------------------------------------------------------------------------