Hire The World’s
Top Talent On Demand
AI EngineersAndroid DevelopersAngularJS DevelopersBigCommerce DevelopersC# DevelopersC++ DevelopersData Visualization DevelopersDrupal DevelopersFront-end DevelopersHTML5 DevelopersiOS DevelopersJava DevelopersKubernetes DevelopersMagento DevelopersMobile App DevelopersNode.js DevelopersOdoo DevelopersPHP DevelopersPython DevelopersQA EngineersReact.js DevelopersRemote DevelopersRuby on Rails DevelopersSalesforce ConsultantsSalesforce DevelopersShopify DevelopersSoftware DevelopersSquarespace DevelopersSvelte DevelopersTechnical WritersWeb DevelopersWebRTC DevelopersWooCommerce DevelopersWordPress DevelopersWPF Developers

Toptal connects the top 3% of freelance developers all over the world.

Nearly Sorted Initial Order

Animation, code, analysis, and discussion of 8 sorting algorithms on nearly sorted initial order.

← Back to all algorithms and initial conditions

How to use: Press “Play all”, or choose the button for the individual row/column to animate.

InsertionSelectionBubbleShell
Insertion on Nearly Sorted Initial Order
Selection on Nearly Sorted Initial Order
Bubble on Nearly Sorted Initial Order
Shell on Nearly Sorted Initial Order
MergeHeapQuickQuick3
Merge on Nearly Sorted Initial Order
Heap on Nearly Sorted Initial Order
Quick on Nearly Sorted Initial Order
Quick3 on Nearly Sorted Initial Order

DISCUSSION

Sorting nearly sorted data is quite common in practice. Some observations:

  • Insertion sort is the clear winner on this initial condition.
  • Bubble sort is fast, but insertion sort has lower overhead.
  • Shell sort is fast because it is based on insertion sort.
  • Merge sort, heap sort, and quick sort do not adapt to nearly sorted data.

Insertion sort provides a O(n2) worst case algorithm that adapts to O(n) time when the data is nearly sorted. One would like an O(n·lg(n)) algorithm that adapts to this situation; smoothsort is such an algorithm, but is complex. Shell sort is the only sub-quadratic algorithm shown here that is also adaptive in this case.

KEY

  • Black values are sorted.
  • Gray values are unsorted.
  • A red triangle marks the algorithm position.
  • Dark gray values denote the current interval (shell, merge, quick).
  • A pair of red triangles marks the left and right pointers (quick).

Preparing for a technical interview? Check out our interview guides.