-------------------------------------------------------------------------------- PROGRAM Mergesort -------------------------------------------------------------------------------- INFORMATION -------------------------------------------------------------------------------- Merge sort (also commonly spelled as mergesort or merge-sort) is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations of merge sort are stable, which means that the relative order of equal elements is the same between the input and output. Merge sort is a divide-and-conquer algorithm that was invented by John von Neumann in 1945. -------------------------------------------------------------------------------- CHARACTERISTICS -------------------------------------------------------------------------------- Best, average, and worst: O(n log n). Space: O(n) for array-based merging. Stable: Yes. -------------------------------------------------------------------------------- LANGUAGES TO IMPLEMENT IN -------------------------------------------------------------------------------- # LANGUAGE IDE -- --------- ---------------------------------------------- 01 Ada GNAT Studio 02 C\C++ Borland C++ 03 C++ .NET Visual Studio 2022 04 C# Visual Studio 2022 05 COBOL OpenCobolIDE 06 Java Eclipse 07 Lua ZeroBrane Studio 08 Pascal Turbo Pascal 09 Perl Notepad++ -> Command Line 10 PowerShell Notepad++ -> Windows PowerShell 11 Python Idle 12 VB .NET Visual Studio 2022 13 x64 Assembly Visual Studio 2022 ---6502 Atari--- 14 Atari BASIC Atari BASIC Editor 15 C Deep Blue C ---68000 Atari--- 16 GFA Basic GFA Basic Atari ST 17 C HiSoft C -------------------------------------------------------------------------------- METHODS/FUNCTIONS (Pseudocode from https://en.wikipedia.org/wiki/Merge_sort) -------------------------------------------------------------------------------- function merge_sort(list m) is // Base case. A list of zero or one elements is sorted, by definition. if length of m ≤ 1 then return m // Recursive case. First, divide the list into equal-sized sublists // consisting of the first half and second half of the list. // This assumes lists start at index 0. var left := empty list var right := empty list for each x with index i in m do if i < (length of m)/2 then add x to left else add x to right // Recursively sort both sublists. left := merge_sort(left) right := merge_sort(right) // Then merge the now-sorted sublists. return merge(left, right) -------------------------------------------------------------------------------- function merge(left, right) is var result := empty list while left is not empty and right is not empty do if first(left) ≤ first(right) then append first(left) to result left := rest(left) else append first(right) to result right := rest(right) // Either left or right may have elements left; consume them. // (Only one of the following loops will actually be entered.) while left is not empty do append first(left) to result left := rest(left) while right is not empty do append first(right) to result right := rest(right) return result -------------------------------------------------------------------------------- SEE ALSO: Heapsort for Loading/Saving files -------------------------------------------------------------------------------- MAIN: ======MERGESORT [LANGUAGE]====== Load Perform Save ==========RUN COMPLETE========== MERGESORT TOOK %f:6 SECONDS. ================================